結果
問題 | No.1956 猫の額 |
ユーザー | testestest |
提出日時 | 2022-04-10 05:07:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,886 ms / 10,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 4,422 ms |
コンパイル使用メモリ | 268,592 KB |
実行使用メモリ | 6,920 KB |
最終ジャッジ日時 | 2023-10-20 17:57:24 |
合計ジャッジ時間 | 30,743 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,960 ms
6,920 KB |
testcase_01 | AC | 126 ms
6,916 KB |
testcase_02 | AC | 1,945 ms
6,920 KB |
testcase_03 | AC | 160 ms
6,916 KB |
testcase_04 | AC | 2,773 ms
6,920 KB |
testcase_05 | AC | 2,290 ms
6,920 KB |
testcase_06 | AC | 2,886 ms
6,920 KB |
testcase_07 | AC | 1,437 ms
6,920 KB |
testcase_08 | AC | 1,497 ms
6,224 KB |
testcase_09 | AC | 196 ms
6,548 KB |
testcase_10 | AC | 1,369 ms
5,884 KB |
testcase_11 | AC | 630 ms
4,920 KB |
testcase_12 | AC | 1,416 ms
5,536 KB |
testcase_13 | AC | 20 ms
4,348 KB |
testcase_14 | AC | 272 ms
4,348 KB |
testcase_15 | AC | 131 ms
6,612 KB |
testcase_16 | AC | 1,533 ms
6,576 KB |
testcase_17 | AC | 131 ms
6,920 KB |
testcase_18 | AC | 313 ms
6,920 KB |
testcase_19 | AC | 1,040 ms
6,920 KB |
testcase_20 | AC | 1,061 ms
6,920 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; ll garner(vector<ll>&r,vector<ll>&m,int M){ int n=r.size(); vector<ll>k(n); for(int i=0;i<n;i++){ modint::set_mod(m[i]); modint a=0,b=1; for(int j=0;j<i;j++){ a+=b*k[j]; b*=m[j]; } k[i]=((r[i]-a+m[i])/b).val(); } modint::set_mod(M); modint a=0,b=1; for(int i=0;i<n;i++){ a+=b*k[i]; b*=m[i]; } return a.val(); } int S; vector<int>A; vector<ll> solve(int P,int c){ modint::set_mod(P); modint g=internal::primitive_root_constexpr(P); modint z=g.pow(P/c); vector<ll>ans(S+1); modint zeta=1; for(int zeta_i=0;zeta_i<c;zeta_i++,zeta*=z){ vector<modint>temp(S+1); temp[0]=1; int sum=0; for(int i=0;i<A.size();i++){ for(int j=sum;j>=0;j--)temp[j+A[i]]+=temp[j]*zeta; sum+=A[i]; } for(int i=0;i<=S;i++)ans[i]+=temp[i].val(); } int invc=(modint(1)/c).val(); for(int i=0;i<=S;i++)ans[i]=ans[i]%P*invc%P; ans[0]=0; return ans; } int main(){ int N,C,mod; cin >> N >> mod >> C; A.resize(N); for(int i=0;i<N;i++)cin >> A[i]; for(int i=0;i<N;i++)S+=A[i]; int CC=2*C>=N?C:N-C; int P=1000000000/CC*CC+1; vector<ll>Ps(4); vector<vector<ll>>ans(4); for(int i=0;i<4;i++,P+=CC){ while(!internal::is_prime_constexpr(P))P+=CC; Ps[i]=P; ans[i]=solve(P,CC); } for(int i=1;i<=S;i++){ vector<ll>r(4); for(int j=0;j<4;j++)r[j]=ans[j][2*C>=N?i:S-i]; ll ret=garner(r,Ps,mod); if(i==S&&2*C==N)ret=(ret-1+mod)%mod; if(i!=1)cout << ' '; cout << ret; } cout << '\n'; }