結果
問題 | No.1956 猫の額 |
ユーザー | testestest |
提出日時 | 2022-04-10 05:53:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,148 ms / 10,000 ms |
コード長 | 1,714 bytes |
コンパイル時間 | 4,653 ms |
コンパイル使用メモリ | 270,032 KB |
実行使用メモリ | 6,920 KB |
最終ジャッジ日時 | 2023-10-20 17:58:37 |
合計ジャッジ時間 | 32,917 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,082 ms
6,920 KB |
testcase_01 | AC | 122 ms
6,916 KB |
testcase_02 | AC | 2,089 ms
6,920 KB |
testcase_03 | AC | 161 ms
6,916 KB |
testcase_04 | AC | 2,976 ms
6,920 KB |
testcase_05 | AC | 2,471 ms
6,920 KB |
testcase_06 | AC | 3,148 ms
6,920 KB |
testcase_07 | AC | 1,568 ms
6,920 KB |
testcase_08 | AC | 1,633 ms
6,224 KB |
testcase_09 | AC | 213 ms
6,548 KB |
testcase_10 | AC | 1,434 ms
5,884 KB |
testcase_11 | AC | 699 ms
4,920 KB |
testcase_12 | AC | 1,515 ms
5,536 KB |
testcase_13 | AC | 20 ms
4,348 KB |
testcase_14 | AC | 304 ms
4,348 KB |
testcase_15 | AC | 136 ms
6,612 KB |
testcase_16 | AC | 1,692 ms
6,576 KB |
testcase_17 | AC | 137 ms
6,920 KB |
testcase_18 | AC | 338 ms
6,920 KB |
testcase_19 | AC | 1,153 ms
6,920 KB |
testcase_20 | AC | 1,154 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,vector<vector<ll>>&b,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; for(int j=0;j<i;j++)a+=b[i][j]*k[j]; k[i]=((r[i]-a+m[i])/b[i][i]).val(); } modint::set_mod(M); modint a=0; for(int i=0;i<n;i++)a+=b[n][i]*k[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); } Ps.push_back(mod); vector<vector<ll>>b(5); b[0].push_back(1); for(int i=1;i<5;i++){ b[i].push_back(1); for(int j=0;j<i;j++)b[i].push_back(b[i].back()*Ps[j]%Ps[i]); } 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,b,mod); if(i==S&&2*C==N)ret=(ret-1+mod)%mod; if(i!=1)cout << ' '; cout << ret; } cout << '\n'; }