제출 #1349764

#제출 시각아이디문제언어결과실행 시간메모리
1349764Jawad_Akbar_JJKpart (eJOI21_kpart)C++20
0 / 100
2093 ms520 KiB
#include <iostream>

using namespace std;
int dp[1<<17], cnt[1<<10], a[1<<10], mod = 1e9 + 7;

void Add(int &A, int B){
	A += B;
	if (A >= mod)
		A -= mod;
}

int main(){
	int t, n, ans;
	cin>>t;
	while (t--){
		cin>>n;

		for (int i=1;i<=n;i++)
			cin>>a[i];
		
		dp[1] = 1, ans = 0;
		for (int k=2;k<=n;k++){
			int s = 0;
			cnt[k] = k - 1;
			for (int i=1;i<=n+k;i++){
				if (i > k){
					for (int j=a[i-k];j <= s;j++)
						Add(dp[j], mod - dp[j - a[i-k]]);
					s -= a[i - k];
				}
				if (i <= n){
					for (int j=s;j + 1;j--)
						Add(dp[j+a[i]], dp[j]);
					s += a[i];
				}

				if (i >= k and i <= n and (s & 1) == 0)
					cnt[k] += (dp[s / 2] > 0);
			}
			ans += cnt[k] == n;
		}

		cout<<ans<<' ';
		for (int k=1;k<=n;k++)
			if (cnt[k] == n)
				cout<<k<<' ';
		cout<<'\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...