結果
問題 |
No.2709 1975 Powers
|
ユーザー |
|
提出日時 | 2024-03-31 15:08:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 718 ms / 2,000 ms |
コード長 | 2,054 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 179,144 KB |
実行使用メモリ | 24,064 KB |
最終ジャッジ日時 | 2024-09-30 20:18:22 |
合計ジャッジ時間 | 12,347 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include "bits/stdc++.h" /* #include "boost/multiprecision/cpp_int.hpp" namespace mp = boost::multiprecision; using i128=mp::cpp_int; */ using namespace std; typedef long long ll; typedef int64_t i64; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<ll> vll; typedef vector<vll> vvll; typedef vector<vvll> vvvll; typedef vector<string> vs; typedef vector<char> vc; typedef vector<vc> vvc; typedef vector<double> vd; typedef vector<vd> vvd; #define rep(i,a,n) for(ll i=a;i<n;i++) #define drep(i,a,n) for(int i=a;i>n;i--) #define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl; #define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl; #define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl; #define iINF 1000000007 #define lINF 10000000000007 #define llINF 4000000000000000007 #define all(x) x.begin(),x.end() #define so(x) sort(all(x)) #define re(x) reverse(all(x)) const double PI = acos(-1); //累乗余り ll modexpo(ll x,ll n,ll m){ if(x==0) return 0; x%=m; ll ans=1; ll change=x; while(n>0){ if(n%2==1){ans*=change; ans%=m;} change*=change; change%=m; n/=2; } return ans; } int main(){ ll n,p,q; cin>>n>>p>>q; vll a(n); rep(i,0,n) cin>>a[i]; so(a); vvvll dp(2,vvll(p,vll(5))); dp[0][0][0]=1; rep(i,1,n+1){ ll I=i%2,J=(i+1)%2; vll mod(5); mod[1]=modexpo(10,a[i-1],p); mod[2]=modexpo(9,a[i-1],p); mod[3]=modexpo(7,a[i-1],p); mod[4]=modexpo(5,a[i-1],p); rep(j,0,p){ rep(k,0,5){ dp[I][j][k]=dp[J][j][k]; } dp[I][j][1]+=dp[J][(j-mod[1]+p)%p][0]; dp[I][j][2]+=dp[J][(j-mod[2]+p)%p][1]; dp[I][j][3]+=dp[J][(j-mod[3]+p)%p][2]; dp[I][j][4]+=dp[J][(j-mod[4]+p)%p][3]; } /*rep(j,0,p){ rep(k,0,5) cout<<dp[I][j][k]<<" "; cout<<endl; } cout<<endl<<endl;*/ } cout<<dp[n%2][q][4]<<endl; }