結果
| 問題 | No.215 素数サイコロと合成数サイコロ (3-Hard) |
| ユーザー |
 LayCurse
|
| 提出日時 | 2015-05-10 20:18:19 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 12,410 bytes |
| コンパイル時間 | 1,511 ms |
| コンパイル使用メモリ | 167,296 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-05 22:01:33 |
| 合計ジャッジ時間 | 1,892 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
コンパイルメッセージ
main.cpp: In member function ‘unsigned int mint::setmod(unsigned int)’:
main.cpp:41:520: warning: no return statement in function returning non-void [-Wreturn-type]
41 | unsigned setmod(unsigned m){W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;}}
| ^
main.cpp: In function ‘void reader(double*)’:
main.cpp:15:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
15 | void reader(double *x){scanf("%lf",x);}
| ~~~~~^~~~~~~~~
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
char memarr[27000000]; void *mem = memarr;
#define MD 1000000007
struct mint{
static unsigned md, W, R, Rinv, mdninv, RR;
unsigned val;
mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);}
unsigned setmod(unsigned m){W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;}}
unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);}
unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}
unsigned get(){return reduce(val);}
mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();}
mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mint operator/(mint a){return mint(*this)/=a;}
mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);}
mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);}
mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;}
operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();}
mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;}
mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;}
mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;}
mint mval[10000], minv[10000];
void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;}
void mfft(int n, mint x[], mint root, void *mem){int i,j,X,Y,Z,s=1;mint I,J,K,a,b,c,d,A,B,C,D,t,*y=(mint*)mem;t=root.pw((mint::md-1)/4*3);root=root.pw((mint::md-1)/n);while(n>2){X=n/4;Y=X+X;Z=X+Y;I.val=mint::R;rep(i,X){J=I*I;K=I*J;rep(j,s)a=x[j+s*i],b=x[j+s*(i+X)],c=x[j+s*(i+Y)],d=x[j+s*(i+Z)],A=a+c,B=a-c,C=b+d,D=(b-d)*t,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=I*(B-D),y[j+s*(4*i+2)]=J*(A-C),y[j+s*(4*i+3)]=K*(B+D);I*=root;}n/=4;s*=4;root*=root;root*=root;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;root*=root;swap(x,y);}rep(i,s)y[i]=x[i];}
void mfftinv(int n, mint x[], mint root, void *mem){int i,j,X,Y,Z,s=1;mint I,J,K,a,b,c,d,A,B,C,D,t,*y=(mint*)mem;root=root.inverse();t=root.pw((mint::md-1)/4);root=root.pw((mint::md-1)/n);while(n>2){X=n/4;Y=X+X;Z=X+Y;I.val=mint::R;rep(i,X){J=I*I;K=I*J;rep(j,s)a=x[j+s*i],b=x[j+s*(i+X)],c=x[j+s*(i+Y)],d=x[j+s*(i+Z)],A=a+c,B=a-c,C=b+d,D=(b-d)*t,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=I*(B+D),y[j+s*(4*i+2)]=J*(A-C),y[j+s*(4*i+3)]=K*(B-D);I*=root;}n/=4;s*=4;root*=root;root*=root;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;root*=root;swap(x,y);}rep(i,s)y[i]=x[i];}
void gmodcomvolutionsGetData(int num, int md[], int root[], int inv[]){int i,j,k;static int A[5]={1004535809,1007681537,1012924417,1045430273,1051721729},B[5]={3,3,5,3,6},C[5][5]={{},{335894166},{253231225,405169960},{26805930,551754894,843088962},{303830744,325532940,568498259,175287122}};rep(i,num)md[i]=A[i];rep(i,num)root[i]=B[i];rep(i,num)rep(j,i)inv[i*num+j]=C[i][j];}
template<class S, class T, class U> void gmodconvolution(S A[], int As, T B[], int Bs, U res[], int Rs, void *mem, int md, int num=3){int i,j,k,m,n,q,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);n=max(As+Bs,Rs);for(q=1;q<n;q*=2);a=(mint**)(z+num*num);a[0]=(mint*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+q;mem=a[num]+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[j][i]=A[i];rep(i,Bs)a[num][i]=B[i];REP(i,As,q)a[j][i].val=0;REP(i,Bs,q)a[num][i].val=0;R=y[j];mfft(q,a[j],R,mem);mfft(q,a[num],R,mem);rep(i,q)a[j][i]*=a[num][i];r=mint(q).inverse();mfftinv(q,a[j],R,mem);rep(i,Rs)a[j][i]*=r;rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
template<class S, class T> void gmodconvolution(S A[], int As, T res[], int Rs, void *mem, int md, int num=3){int i,j,k,m,n,q,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);n=max(As+As,Rs);for(q=1;q<n;q*=2);a=(mint**)(z+num*num);a[0]=(mint*)(a+num);REP(i,1,num)a[i]=a[i-1]+q;mem=a[num-1]+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[j][i]=A[i];REP(i,As,q)a[j][i].val=0;R=y[j];mfft(q,a[j],R,mem);rep(i,q)a[j][i]*=a[j][i];r=mint(q).inverse();mfftinv(q,a[j],R,mem);rep(i,Rs)a[j][i]*=r;rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
template<class S> void gmodconvolutionPreCalc(S A[], int As, mint res[], int Rs, void *mem, int md, int num=3, int domultiply=1){int i,j,q,*x,*y,*z,*w;mint r,R,*a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);q=Rs;a=(mint*)(z+num*num);mem=a+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[i]=A[i];REP(i,As,q)a[i].val=0;R=y[j];mfft(q,a,R,mem);rep(i,Rs)res[j*Rs+i]=a[i];if(domultiply){r=mint(q).inverse();rep(i,Rs)res[j*Rs+i]*=r;}}r.setmod(md);}
template<class T, class U> void gmodconvolutionWithPreCalc(mint A[], int As, T B[], int Bs, U res[], int Rs, void *mem, int md, int num=3, int ordered=1, int domultiply=0){int i,j,q,k,m,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);q=As;a=(mint**)(z+num*num);a[0]=(mint*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+q;mem=a[num]+q;rep(j,num){r.setmod(x[j]);rep(i,q)a[j][i]=A[j*q+i];rep(i,Bs)a[num][i]=B[i];REP(i,Bs,q)a[num][i].val=0;R=y[j];mfft(q,a[num],R,mem);rep(i,q)a[j][i]*=a[num][i];mfftinv(q,a[j],R,mem);if(domultiply){r=mint(q).inverse();rep(i,Rs)a[j][i]*=r;}rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
int modconvolutionGetLength(int As, int Bs, int Rs){int n=max(As+Bs,Rs),res;for(res=1;res<n;res*=2);return res;}
template<class T> void Kitamasa_mg_reduce(int a[], int y, T c[], int d, int md, ll L, int h, int o, mint **calc, int *q, int *p, void *mem){int i,j,t,l,E,*D=(int*)mem;ll*Z=(ll*)(D+2*d);mem=(void*)(Z+y);rep(i,y)Z[i]=a[i];for(j=o-1;j>=0;j--){E=y-d;l=q[j]-d;if(E<2*l)continue;t=E-2*l;gmodconvolutionWithPreCalc(calc[j],p[j],Z+y-l,l,D,d+l,mem,md,h);rep(i,d+l){Z[t+i+1]+=D[i];if(Z[t+i]>=md)Z[t+i]-=md;}y-=l;}while(y>d){y--;if(Z[y]>=md)Z[y]%=md;rep(i,d){Z[y-d+i]+=Z[y]*(ll)c[i];if(Z[y-d+i]>=L)Z[y-d+i]%=md;}}rep(i,y)if(Z[i]>=md)Z[i]%=md;rep(i,y)a[i]=Z[i];}
template<class S, class T> ll Kitamasa_mg(ll n, S a[], T c[], int d, int md, void *mem){int i,j,m,l,t,y,s,*A,*D,*E,o=0,*R,*W,h;mint **Q;ll L=((1ULL<<63)-1)-(ull)(md-1)*(md-1),*Z,C;if(n<d)return a[n];h=ceil((log(2)+log(d)+2*log(md))/log(1004535809)+1e-5);R=(int*)mem;W=R+25;Q=(mint**)(W+25);A=(int*)(Q+25);mem=A+2*d;for(i=20;i>=0;i--)if(d/(1<<i)>=500||i==0){m=d+d/(1<<i);rep(j,m)A[j]=0;A[m-1]=1;Kitamasa_mg_reduce(A,m,c,d,md,L,h,o,Q,R,W,mem);R[o]=m;l=m-d;W[o]=modconvolutionGetLength(d,l,d+l);Q[o]=(mint*)mem;mem=Q[o]+W[o]*h;gmodconvolutionPreCalc(A,d,Q[o],W[o],mem,md,h);o++;}Z=(ll*)mem;y=0;for(;;){Z[y++]=n;if(n<2*d)break;n/=2;}D=(int*)(Z+y);E=D+4*d;mem=E+2*d;rep(i,2*d)A[i]=0;A[Z[--y]]=1;while(y--){gmodconvolution(A,2*d,D,4*d,mem,md,h);s=4*d;j=o-1;rep(m,2){l=R[j]-d;t=s-d-2*l;gmodconvolutionWithPreCalc(Q[j],W[j],D+s-l,l,E,d+l,mem,md,h);rep(i,d+l){D[t+i+1]+=E[i];if(D[t+i+1]>=md)D[t+i+1]-=md;}s-=l;}rep(i,2*d)A[i]=D[i];if(Z[y]!=Z[y+1]*2){C=A[2*d-1];for(i=2*d-1;i;i--)A[i]=A[i-1]; A[0]=0;rep(i,d)A[d+i]=(A[d+i]+(ll)c[i]*C)%md;}}Kitamasa_mg_reduce(A,2*d,c,d,md,L,h,o,Q,R,W,mem);C=0;rep(i,d){C+=(ll)a[i]*A[i];if(C>=L)C%=md;}if(C>=md)C%=md;return C;}
int pp[6] = {2,3,5,7,11,13};
int cc[6] = {4,6,8,9,10,12};
mint dp_p[301][4200], dp_c[301][4200];
mint a[9400], c[9400];
int aaa[9400], ccc[9400];
int main(){
int i, j, k, d;
ll N; int P, C;
int res;
mint_init();
dp_p[0][0] = dp_c[0][0] = mval[1];
rep(k,6) rep(i,300) rep(j,4200) if(dp_p[i][j]) dp_p[i+1][j+pp[k]] += dp_p[i][j];
rep(k,6) rep(i,300) rep(j,4200) if(dp_c[i][j]) dp_c[i+1][j+cc[k]] += dp_c[i][j];
reader(&N);
reader(&P, &C);
d = P * pp[5] + C * cc[5];
rep(i,d) a[i] = mval[1];
rep(i,4200) if(dp_p[P][i]) rep(j,4200) if(dp_c[C][j]) c[d-i-j] += dp_p[P][i] * dp_c[C][j];
rep(i,d) aaa[i]=(int)a[i];
rep(i,d) ccc[i]=(int)c[i];
res = Kitamasa_mg(N+d-1, aaa, ccc, d, MD, mem);
writer(res, '\n');
return 0;
}