QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#769938 | #9436. Some Sum of Subset | woodie_0064# | TL | 0ms | 0kb | C++20 | 1.2kb | 2024-11-21 19:58:46 | 2024-11-21 19:58:47 |
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 3;
const int mod = 998244353;
typedef long long ll;
void work(){
int n,m;cin >> n >> m;
vector <int> a(n + 1);
for(int i = 1;i <= n;i++) cin >> a[i];
sort(a.begin() + 1,a.end(),[&](int &x,int &y) {
return x > y;
});
vector <vector <int>> C(n + 1,vector <int> (n + 1));
C[0][0] = 1;
auto add = [&] (int &x,int y) {
x += y;
if(x >= mod) x -= mod;
};
for(int i = 1;i <= n;i++) {
C[i][0] = 1;
for(int j = 1;j <= i;j++) {
C[i][j] = C[i - 1][j - 1];
add(C[i][j],C[i - 1][j]);
}
}
vector <vector <int>> f(n + 1,vector <int> (m + 1));
f[0][0] = 1;
vector <int> ans(n + 1);
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= m;j++) add(f[i][min(j + a[i],m)],f[i - 1][j]);
for(int j = 0;j <= n - i;j++) add(ans[j],1LL * f[i][m] * C[n - i][j] % mod);
for(int j = 0;j <= m;j++) add(f[i][j],f[i - 1][j]);
}
for(auto &x : ans) cout <<x << '\n';
}
int main(){
freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
work();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 7 3 1 5 2