結果
問題 | No.2709 1975 Powers |
ユーザー |
|
提出日時 | 2024-03-31 13:59:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,909 bytes |
コンパイル時間 | 1,504 ms |
コンパイル使用メモリ | 174,596 KB |
実行使用メモリ | 24,028 KB |
最終ジャッジ日時 | 2024-09-30 18:46:44 |
合計ジャッジ時間 | 12,016 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 WA * 16 |
ソースコード
#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){vll mod(5);mod[1]=modexpo(10,a[i],p);mod[2]=modexpo(9,a[i],p);mod[3]=modexpo(7,a[i],p);mod[4]=modexpo(5,a[i],p);ll I=i%2,J=(i+1)%2;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];}}cout<<dp[n%2][q][4]<<endl;}