結果
| 問題 |
No.215 素数サイコロと合成数サイコロ (3-Hard)
|
| コンテスト | |
| ユーザー |
 LayCurse
|
| 提出日時 | 2015-05-10 04:16:02 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 15,963 bytes |
| コンパイル時間 | 1,279 ms |
| コンパイル使用メモリ | 166,772 KB |
| 実行使用メモリ | 9,800 KB |
| 最終ジャッジ日時 | 2024-07-05 21:22:11 |
| 合計ジャッジ時間 | 2,560 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 2 |
コンパイルメッセージ
main.cpp: In member function ‘unsigned int mint::setmod(unsigned int)’:
main.cpp:83:3: warning: no return statement in function returning non-void [-Wreturn-type]
83 | }
| ^
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');}
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 inverse(){
int a = val, b = md, u = 1, v = 0, t;
mint res;
while(b){
t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if(u < 0) u += md;
res.val = (ull)u*RR % md;
return res;
}
mint pw(ull b){
mint a(*this), res;
res.val = R;
while(b){
if(b&1) res *= a;
b >>= 1;
a *= a;
}
return res;
}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
ull pw(ull a, ull b, ull m){ull r=1;while(b){if(b&1)r=r*a%m;b>>=1;a=a*a%m;}return r;}
void mfft(int n, mint x[], mint root, void *mem){
int i, j;
int n1, n2, n3, step = 1;
mint w1, w2, w3, a, b, c, d, aa, bb, cc, dd, tmp, *y = (mint*)mem;
tmp = root.pw((mint::md-1)/4*3);
root = root.pw((mint::md-1)/n);
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
w1.val = mint::R;
rep(i,n1){
w2 = w1*w1;
w3 = w1*w2;
rep(j,step){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = (b - d) * tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb - dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb + dd);
}
w1 *= root;
}
n /= 4;
step *= 4;
root *= root;
root *= root;
swap(x,y);
}
if(n==2){
rep(i,step){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
root *= root;
swap(x,y);
}
rep(i,step) y[i] = x[i];
}
void mfftinv(int n, mint x[], mint root, void *mem){
int i, j;
int n1, n2, n3, step = 1;
mint w1, w2, w3, a, b, c, d, aa, bb, cc, dd, tmp, *y = (mint*)mem;
root = root.inverse();
tmp = root.pw((mint::md-1)/4);
root = root.pw((mint::md-1)/n);
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
w1.val = mint::R;
rep(i,n1){
w2 = w1*w1;
w3 = w1*w2;
rep(j,step){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = (b - d) * tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb + dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb - dd);
}
w1 *= root;
}
n /= 4;
step *= 4;
root *= root;
root *= root;
swap(x,y);
}
if(n==2){
rep(i,step){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
root *= root;
swap(x,y);
}
rep(i,step) y[i] = x[i];
}
void gmodcomvolutionsGetData(int num, int md[], int root[], int inv[]){
int i, j, k;
static int d_md[5] = {1004535809,1007681537,1012924417,1045430273,1051721729};
static int d_rt[5] = {3,3,5,3,6};
static int d_iv[5][5] = {{},{335894166},{253231225,405169960},{26805930,551754894,843088962},{303830744,325532940,568498259,175287122}};
rep(i,num) md[i] = d_md[i];
rep(i,num) root[i] = d_rt[i];
rep(i,num) rep(j,i) inv[i*num+j] = d_iv[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, n2;
mint r, rt;
int *tmd, *trt, *tiv, *val;
mint **a;
val = (int*)mem;
tmd = val+num;
trt = tmd+num;
tiv = trt+num;
gmodcomvolutionsGetData(num, tmd, trt, tiv);
n = max(As+Bs, Rs);
for(n2=1;n2<n;n2*=2);
a = (mint**)(tiv+num*num);
a[0] = (mint*)(a+num+1);
REP(i,1,num+1) a[i] = a[i-1] + n2;
mem = a[num]+n2;
rep(j,num){
r.setmod(tmd[j]);
rep(i,As) a[j][i] = A[i];
rep(i,Bs) a[num][i] = B[i];
REP(i,As,n2) a[j][i].val = 0;
REP(i,Bs,n2) a[num][i].val = 0;
rt = trt[j];
mfft(n2, a[j], rt, mem);
mfft(n2, a[num], rt, mem);
rep(i,n2) a[j][i] *= a[num][i];
r = mint(n2).inverse();
mfftinv(n2, a[j], rt, 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) val[i] = a[i][m].val;
rep(i,num) rep(j,i){
k = val[i] - val[j];
if(k < 0) k += tmd[i];
val[i] = (ll)k*tiv[i*num+j]%tmd[i];
}
k = 0;
for(i=num-1;i>=0;i--){
k = ((ll)k*tmd[i] + val[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, n2;
mint r, rt;
int *tmd, *trt, *tiv, *val;
mint **a;
val = (int*)mem;
tmd = val+num;
trt = tmd+num;
tiv = trt+num;
gmodcomvolutionsGetData(num, tmd, trt, tiv);
n = max(As+As, Rs);
for(n2=1;n2<n;n2*=2);
a = (mint**)(tiv+num*num);
a[0] = (mint*)(a+num);
REP(i,1,num) a[i] = a[i-1] + n2;
mem = a[num-1]+n2;
rep(j,num){
r.setmod(tmd[j]);
rep(i,As) a[j][i] = A[i];
REP(i,As,n2) a[j][i].val = 0;
rt = trt[j];
mfft(n2, a[j], rt, mem);
rep(i,n2) a[j][i] *= a[j][i];
r = mint(n2).inverse();
mfftinv(n2, a[j], rt, 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) val[i] = a[i][m].val;
rep(i,num) rep(j,i){
k = val[i] - val[j];
if(k < 0) k += tmd[i];
val[i] = (ll)k*tiv[i*num+j]%tmd[i];
}
k = 0;
for(i=num-1;i>=0;i--){
k = ((ll)k*tmd[i] + val[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, n2;
mint r, rt;
int *tmd, *trt, *tiv, *val;
mint *a;
val = (int*)mem;
tmd = val+num;
trt = tmd+num;
tiv = trt+num;
gmodcomvolutionsGetData(num, tmd, trt, tiv);
n2 = Rs;
a = (mint*)(tiv+num*num);
mem = a+n2;
rep(j,num){
r.setmod(tmd[j]);
rep(i,As) a[i] = A[i];
REP(i,As,n2) a[i].val = 0;
rt = trt[j];
mfft(n2, a, rt, mem);
rep(i,Rs) res[j*Rs+i] = a[i];
if(domultiply){
r = mint(n2).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, n2, k, m;
mint r, rt;
int *tmd, *trt, *tiv, *val;
mint **a;
val = (int*)mem;
tmd = val+num;
trt = tmd+num;
tiv = trt+num;
gmodcomvolutionsGetData(num, tmd, trt, tiv);
n2 = As;
a = (mint**)(tiv+num*num);
a[0] = (mint*)(a+num+1);
REP(i,1,num+1) a[i] = a[i-1] + n2;
mem = a[num]+n2;
rep(j,num){
r.setmod(tmd[j]);
rep(i,n2) a[j][i] = A[j*n2+i];
rep(i,Bs) a[num][i] = B[i];
REP(i,Bs,n2) a[num][i].val = 0;
rt = trt[j];
mfft(n2, a[num], rt, mem);
rep(i,n2) a[j][i] *= a[num][i];
mfftinv(n2, a[j], rt, mem);
if(domultiply){
r = mint(n2).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) val[i] = a[i][m].val;
rep(i,num) rep(j,i){
k = val[i] - val[j];
if(k < 0) k += tmd[i];
val[i] = (ll)k*tiv[i*num+j]%tmd[i];
}
k = 0;
for(i=num-1;i>=0;i--){
k = ((ll)k*tmd[i] + val[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;}
void Kitamasa_g_reduce(mint a[], int sz, mint c[], int d, int md, ll limit, int num, int calsz, mint **calc, int *beflen, int *aftlen, void *mem){
int i, j, st, len, ex;
int *D = (int*)mem;
int *send = D+2*d;
mint *arr = (mint*)(send+2*d);
mem = (void*)(arr + sz);
arr[0].setmod(md);
rep(i,sz) arr[i] = a[i];
for(j=calsz-1;j>=0;j--){
ex = sz - d;
len = beflen[j] - d;
if(ex < 2*len) continue;
st = ex - 2*len;
rep(i,len) send[i] = arr[sz-len+i].get();
gmodconvolutionWithPreCalc(calc[j], aftlen[j], send, len, D, d+len, mem, md, num);
rep(i,d+len){
arr[st+i+1] += D[i];
}
sz -= len;
}
while(sz > d){
sz--;
rep(i,d){
arr[sz-d+i] += arr[sz] * c[i];
}
}
rep(i,sz) a[i] = arr[i].get();
}
template<class S, class T>
int Kitamasa_g(ll n, S a[], T c[], int d, int md, void *mem){
int i, j, m, len, st;
ll limit = ((1ULL<<63)-1)-(ull)(md-1)*(md-1);
ll *arr; int sz, s;
mint *A;
mint *D, *E;
int reduce_size = 0;
int *reduce_len;
int *reduce_calc_len;
mint **reduce_calc;
mint *aa, *cc;
mint C;
int num;
int *send, *recv;
double chk;
if(n < d) return a[n];
chk = (log(2) + log(d) + 2 * log(md)) / log(1004535809);
num = ceil(chk+1e-5);
send = (int*)mem;
recv = send + 4*d;
aa = (mint*)(recv+4*d);
cc = aa + d;
aa[0].setmod(md);
rep(i,d) aa[i] = a[i];
rep(i,d) cc[i] = c[i];
reduce_len = (int*)(cc+d);
reduce_calc_len = reduce_len + 25;
reduce_calc = (mint**)(reduce_calc_len+25);
A = (mint*)(reduce_calc+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_g_reduce(A, m, cc, d, md, limit, num, reduce_size, reduce_calc, reduce_len, reduce_calc_len, mem);
reduce_len[reduce_size] = m;
len = m - d;
reduce_calc_len[reduce_size] = modconvolutionGetLength(d, len, d+len);
reduce_calc[reduce_size] = (mint*)mem;
mem = reduce_calc[reduce_size] + reduce_calc_len[reduce_size]*num;
rep(j,d) send[j] = A[j].get();
gmodconvolutionPreCalc(send, d, reduce_calc[reduce_size], reduce_calc_len[reduce_size], mem, md, num);
reduce_size++;
}
arr = (ll*)mem;
sz = 0;
for(;;){
arr[sz++] = n;
if(n < 2*d) break;
n /= 2;
}
D = (mint*)(arr+sz);
E = D + 4*d;
mem = E + 2*d;
rep(i,2*d) A[i] = 0;
A[arr[--sz]].val = mint::R;
while(sz--){
rep(i,2*d) send[i] = A[i].get();
gmodconvolution(send, 2*d, D, 4*d, mem, md, num);
s = 4*d;
j = reduce_size - 1;
rep(m,2){
len = reduce_len[j] - d;
st = s - d - 2*len;
rep(i,len) send[i] = D[s-len+i].get();
gmodconvolutionWithPreCalc(reduce_calc[j], reduce_calc_len[j], send, len, recv, d+len, mem, md, num);
rep(i,d+len) E[i] = recv[i];
rep(i,d+len){
D[st+i+1] += E[i];
}
s -= len;
}
rep(i,2*d) A[i] = D[i];
if(arr[sz]!=arr[sz+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] += cc[i] * C;
}
}
Kitamasa_g_reduce(A, 2*d, cc, d, md, limit, num, reduce_size, reduce_calc, reduce_len, reduce_calc_len, mem);
C = 0;
rep(i,d){
C += aa[i] * A[i];
}
return C.get();
}
char memarr[127000000]; void *mem = memarr;
#define MD 1000000007
int pp[6] = {2,3,5,7,11,13};
int cc[6] = {4,6,8,9,10,12};
int dp_p[301][4200], dp_c[301][4200];
int a[9400], c[9400];
int main(){
int i, j, k, d;
ll N; int P, C;
int res;
if(0){
int a[100000], b[100000], c[200000];
rep(i,100000) a[i] = b[i] = (1e8) + i;
gmodconvolution(a,100000,c,200000,mem,MD);
writerLn(c[12345]);
return 0;
}
dp_p[0][0] = dp_c[0][0] = 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+1][j+pp[k]] + dp_p[i][j]) % MD;
rep(k,6) rep(i,300) rep(j,4200) if(dp_c[i][j]) dp_c[i+1][j+cc[k]] = (dp_c[i+1][j+cc[k]] + dp_c[i][j]) % MD;
reader(&N);
reader(&P, &C);
d = P * pp[5] + C * cc[5];
rep(i,d) a[i] = 1;
rep(i,4200) if(dp_p[P][i]) rep(j,4200) if(dp_c[C][j]) c[d-i-j] = (c[d-i-j] + (ll)dp_p[P][i] * dp_c[C][j]) % MD;
res = Kitamasa_g(N+d-1, a, c, d, MD, mem);
writer(res, '\n');
return 0;
}