結果
問題 | No.1025 Modular Equation |
ユーザー |
![]() |
提出日時 | 2020-04-10 23:59:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,120 bytes |
コンパイル時間 | 2,811 ms |
コンパイル使用メモリ | 202,612 KB |
実行使用メモリ | 71,744 KB |
最終ジャッジ日時 | 2024-09-16 03:48:57 |
合計ジャッジ時間 | 10,202 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 TLE * 1 -- * 25 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;//template#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rrep(i,a,b) for(int i=(a);i>(b);i--)#define ALL(v) (v).begin(),(v).end()typedef long long int ll;const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }//endtemplate<unsigned mod=1000000007>struct mint {unsigned val;static unsigned get_mod(){return mod;}unsigned inv() const{int tmp,a=val,b=mod,x=1,y=0;while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y);if(x<0)x+=mod; return x;}mint():val(0){}mint(ll x):val(x>=0?x%mod:mod+(x%mod)){}mint pow(ll t){mint res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}mint& operator+=(const mint& x){if((val+=x.val)>=mod)val-=mod;return *this;}mint& operator-=(const mint& x){if((val+=mod-x.val)>=mod)val-=mod; return *this;}mint& operator*=(const mint& x){val=ll(val)*x.val%mod; return *this;}mint& operator/=(const mint& x){val=ll(val)*x.inv()%mod; return *this;}mint operator+(const mint& x)const{return mint(*this)+=x;}mint operator-(const mint& x)const{return mint(*this)-=x;}mint operator*(const mint& x)const{return mint(*this)*=x;}mint operator/(const mint& x)const{return mint(*this)/=x;}bool operator==(const mint& x)const{return val==x.val;}bool operator!=(const mint& x)const{return val!=x.val;}}; using Mint=mint<>;struct factorial {vector<Mint> Fact,Finv,Inv;factorial(int maxx){Fact.resize(maxx); Finv.resize(maxx); Inv.resize(maxx);Fact[0]=Fact[1]=Finv[0]=Finv[1]=Inv[1]=1; unsigned mod=Mint::get_mod();rep(i,2,maxx){Fact[i]=Fact[i-1]*i;Inv[i]=Inv[mod%i]*(mod-mod/i);Finv[i]=Finv[i-1]*Inv[i];}}Mint fact(int n,bool inv=0){if(inv)return Finv[n];else return Fact[n];}Mint inv(int n){return Inv[n];}Mint nPr(int n,int r){if(n<0||n<r||r<0)return Mint(0);else return Fact[n]*Finv[n-r];}Mint nCr(int n,int r){if(n<0||n<r||r<0)return Mint(0);else return Fact[n]*Finv[r]*Finv[n-r];}};template<typename T,unsigned p>struct NTT{vector<T> rt,irt;NTT(int lg=21){unsigned mod=T::get_mod();T prt=p; rt.resize(1<<lg,1); irt.resize(1<<lg,1);rep(w,0,lg){int mask=(1<<w)-1,t=(mod-1)>>w;T g=prt.pow(t),ig=prt.pow(mod-1-t);rep(i,0,mask){rt[mask+i+1]=g*rt[mask+i];irt[mask+i+1]=ig*irt[mask+i];}}}void ntt(vector<T>& f,bool inv=0){int n=f.size();if(inv){for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=i*2)rep(k,0,i){f[i+j+k]*=irt[i*2-1+k]; const T tmp=f[j+k]-f[i+j+k];f[j+k]+=f[i+j+k]; f[i+j+k]=tmp;}T mul=T(n).inv(); rep(i,0,n)f[i]*=mul;}else{for(int i=n>>1;i;i>>=1)for(int j=0;j<n;j+=i*2)rep(k,0,i){const T tmp=f[j+k]-f[i+j+k];f[j+k]+=f[i+j+k]; f[i+j+k]=tmp*rt[i*2-1+k];}}}vector<T> conv(vector<T> a,vector<T> b){int n=a.size()+b.size()-1,m=(n&(n-1)?1<<(32-__builtin_clz(n)):n);a.resize(m); b.resize(m); ntt(a); ntt(b);rep(i,0,m)a[i]*=b[i]; ntt(a,1); a.resize(n); return a;}};using M1=mint<1045430273>; using M2=mint<1051721729>; using M3=mint<1053818881>;NTT<mint<1045430273>,3> N1; NTT<mint<1051721729>,6> N2; NTT<mint<1053818881>,7> N3;vector<Mint> conv(vector<Mint> a,vector<Mint> b){int n=a.size()+b.size()-1; vector<Mint> res(n); vector<int> vals[3];vector<int> aa(a.size()),bb(b.size());rep(i,0,a.size())aa[i]=a[i].val; rep(i,0,b.size())bb[i]=b[i].val;vector<M1> a1(ALL(aa)),b1(ALL(bb)),c1=N1.conv(a1,b1);vector<M2> a2(ALL(aa)),b2(ALL(bb)),c2=N2.conv(a2,b2);vector<M3> a3(ALL(aa)),b3(ALL(bb)),c3=N3.conv(a3,b3);for(M1 x:c1)vals[0].push_back(x.val);for(M2 x:c2)vals[1].push_back(x.val);for(M3 x:c3)vals[2].push_back(x.val);M2 r_12=175287122;M3 r_13=395182206,r_23=526909943,r_1323=461108887;Mint w1=1045430273; Mint w2=571989935;rep(i,0,n){ll a=vals[0][i];ll b=(vals[1][i]+M2::get_mod()-a)*r_12.val%M2::get_mod();ll c=((vals[2][i]+M3::get_mod()-a)*r_1323.val+(M3::get_mod()-b)*r_23.val)%M3::get_mod();res[i]=(a+b*w1.val+c*w2.val);} return res;}int mpow(int x,int k,int m){if(x<=1)return x; int res=1;while(k){if(k&1)res=(1LL*res*x)%m;x=(1LL*x*x)%m; k>>=1;} return res;}int main(){int p,n,k,b; cin>>p>>n>>k>>b;vector<int> a(n); rep(i,0,n)scanf("%d",&a[i]);vector<int> po(p);rep(i,0,p)po[i]=mpow(i,k,p);vector<Mint> dp(b+1); dp[0]=1;rep(i,0,n){vector<Mint> vs(p);rep(j,0,p)vs[(1LL*a[i]*po[j])%p]+=1;dp=conv(dp,vs);rep(j,p,dp.size())dp[j-p]+=dp[j];dp.resize(p);} printf("%d\n",dp[b].val);return 0;}