結果
問題 | No.2709 1975 Powers |
ユーザー |
|
提出日時 | 2024-03-31 13:54:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,798 bytes |
コンパイル時間 | 1,683 ms |
コンパイル使用メモリ | 174,524 KB |
実行使用メモリ | 27,520 KB |
最終ジャッジ日時 | 2024-09-30 18:36:56 |
合計ジャッジ時間 | 5,368 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 24 |
ソースコード
#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(int 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+1); rep(i,1,n+1) cin>>a[i]; vvvll dp(2,vvll(p,vll(5))); dp[0][0][0]=1; rep(i,1,n+1){ int I=i%2,J=(i+1)%2; rep(j,0,p){ rep(k,1,5){ dp[I][j][k]=dp[J][j][k]; } dp[I][j][1]+=dp[J][(j-modexpo(10,a[i],p)+p)%p][0]; dp[I][j][2]+=dp[J][(j-modexpo(9,a[i],p)+p)%p][1]; dp[I][j][3]+=dp[J][(j-modexpo(7,a[i],p)+p)%p][2]; dp[I][j][4]+=dp[J][(j-modexpo(5,a[i],p)+p)%p][3]; } } cout<<dp[n%2][q][4]<<endl; }