結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
コンテスト
ユーザー LayCurse
提出日時 2015-03-24 16:42:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,523 bytes
コンパイル時間 1,462 ms
コンパイル使用メモリ 160,640 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2024-06-29 00:33:08
合計ジャッジ時間 11,698 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

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[301][4200], dp_c[301][4200];
ll a[9700], c[9700];

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

  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] + 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