QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769938#9436. Some Sum of Subsetwoodie_0064#TL 0ms0kbC++201.2kb2024-11-21 19:58:462024-11-21 19:58:47

Judging History

你现在查看的是最新测评结果

  • [2024-11-21 19:58:47]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-21 19:58:46]
  • 提交

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;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

4 7
3 1 5 2

output:


result: