結果
問題 | No.1956 猫の額 |
ユーザー | testestest |
提出日時 | 2022-04-10 06:06:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,994 ms / 10,000 ms |
コード長 | 1,560 bytes |
コンパイル時間 | 4,586 ms |
コンパイル使用メモリ | 268,228 KB |
実行使用メモリ | 5,284 KB |
最終ジャッジ日時 | 2023-10-20 17:59:20 |
合計ジャッジ時間 | 31,595 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,979 ms
5,284 KB |
testcase_01 | AC | 127 ms
5,284 KB |
testcase_02 | AC | 1,941 ms
5,284 KB |
testcase_03 | AC | 163 ms
5,284 KB |
testcase_04 | AC | 2,811 ms
5,284 KB |
testcase_05 | AC | 2,335 ms
5,284 KB |
testcase_06 | AC | 2,994 ms
5,284 KB |
testcase_07 | AC | 1,467 ms
5,284 KB |
testcase_08 | AC | 1,555 ms
4,948 KB |
testcase_09 | AC | 216 ms
5,168 KB |
testcase_10 | AC | 1,408 ms
4,840 KB |
testcase_11 | AC | 689 ms
4,456 KB |
testcase_12 | AC | 1,442 ms
4,628 KB |
testcase_13 | AC | 21 ms
4,348 KB |
testcase_14 | AC | 309 ms
4,348 KB |
testcase_15 | AC | 142 ms
5,208 KB |
testcase_16 | AC | 1,654 ms
5,184 KB |
testcase_17 | AC | 170 ms
5,284 KB |
testcase_18 | AC | 357 ms
5,284 KB |
testcase_19 | AC | 1,094 ms
5,284 KB |
testcase_20 | AC | 1,091 ms
5,284 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; int garner(vector<int>&r,vector<int>&m,int M){ int n=r.size(); vector<int>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<int> solve(int P,int c){ modint::set_mod(P); modint g=internal::primitive_root_constexpr(P); modint z=g.pow(P/c); vector<int>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]=(ans[i]+temp[i].val())%P; } ll invc=(modint(1)/c).val(); for(int i=0;i<=S;i++)ans[i]=ans[i]*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<int>Ps(4); vector<vector<int>>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<int>r(4); for(int j=0;j<4;j++)r[j]=ans[j][2*C>=N?i:S-i]; int ret=garner(r,Ps,mod); if(i==S&&2*C==N)ret=(ret-1+mod)%mod; if(i!=1)cout << ' '; cout << ret; } cout << '\n'; }