結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー LayCurseLayCurse
提出日時 2014-11-11 19:59:26
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 220 ms / 3,000 ms
コード長 2,582 bytes
コンパイル時間 1,182 ms
コンパイル使用メモリ 160,764 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-10 02:25:50
合計ジャッジ時間 2,525 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 211 ms
6,812 KB
testcase_01 AC 200 ms
6,940 KB
testcase_02 AC 220 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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(int *x, int *y){reader(x);reader(y);}
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 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);}

#define MD 1000000007

void Kitamasa_mul(ll A[], ll c[], int d, ll md, ll limit, void *mem){int i,j;ll *C=(ll*)mem;rep(i,2*d-1)C[i]=0;rep(i,d)rep(j,d){C[i+j]+=A[i]*A[j];if(C[i+j]>=limit||C[i+j]<=-limit)C[i+j]%=md;}for(i=2*d-2;i>=d;i--){if(C[i]>=md||C[i]<=-md)C[i]%=md;rep(j,d){C[i-d+j]+=C[i]*c[j];if(C[i-d+j]>=limit||C[i-d+j]<=-limit)C[i-d+j]%=md;}}rep(i,d){A[i]=C[i];if(A[i]>=md||A[i]<=-md)A[i]%=md;}}
void Kitamasa_add(ll A[], ll c[], int d, ll md){int i;ll C;C=A[d-1];for(i=d-1;i;i--)A[i]=A[i-1];A[0]=0;rep(i,d){A[i]+=c[i]*C;if(A[i]<-md||A[i]>=md)A[i]%=md;}}
ll Kitamasa(ll n, ll a[], ll c[], int d, ll md, void *mem){int i,z=0;ll s,*A,*r,limit=((1ULL<<63)-1)-(ull)(md-1)*(md-1);r=(ll*)mem;for(;;){r[z++]=n;if(n<d)break;n/=2;}A=r+z;mem=(void*)(A+d);rep(i,d)A[i]=0;A[r[--z]]=1;while(z--){Kitamasa_mul(A,c,d,md,limit,mem);if(r[z]!=r[z+1]*2)Kitamasa_add(A,c,d,md);}s=0;rep(i,d){s+=a[i]*A[i];if(s>=limit||s<=-limit)s%=md;}if(s<=-md||s>=md)s%=md;return s;}

int pp[6] = {2,3,5,7,11,13};
int cc[6] = {4,6,8,9,10,12};

ll dp_p[51][700], dp_c[51][700];
ll a[1400], c[1400];

ll dp[100000];

int main(){
  int i, j, k, d;
  ll N; int P, C;
  int res;
  void *mem = malloc(70000000);

  dp_p[0][0] = dp_c[0][0] = 1;
  rep(k,6) rep(i,50) rep(j,700) 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,50) rep(j,700) 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,700) if(dp_p[P][i]) rep(j,700) if(dp_c[C][j]) c[d-i-j] = (c[d-i-j] + dp_p[P][i] * dp_c[C][j]) % MD;

  res = Kitamasa(N+d-1, a, c, d, MD, mem);
  if(res < 0) res += MD;
  writer(res, '\n');

  return 0;
}
0