結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
ユーザー LayCurseLayCurse
提出日時 2015-05-10 08:49:28
言語 C++11
(gcc 11.4.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 17,060 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 154,516 KB
実行使用メモリ 814,604 KB
最終ジャッジ日時 2023-09-19 09:39:44
合計ジャッジ時間 6,174 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘unsigned int mint::setmod(unsigned int)’:
main.cpp:85:3: warning: no return statement in function returning non-void [-Wreturn-type]
   }
   ^

ソースコード

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(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[127000000]; 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 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;
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;
  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;}



template<class T>
void Kitamasa_g_reduce(int a[], int sz, T 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;
  ll *arr = (ll*)(D+2*d);
  mem = (void*)(arr + sz);

  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;
    gmodconvolutionWithPreCalc(calc[j], aftlen[j], arr+sz-len, len, D, d+len, mem, md, num);
    rep(i,d+len){
      arr[st+i+1] += D[i];
      if(arr[st+i] >= md) arr[st+i] -= md;
    }
    sz -= len;
  }

  while(sz > d){
    sz--;
    if(arr[sz] >= md) arr[sz] %= md;
    rep(i,d){
      arr[sz-d+i] += arr[sz] * (ll)c[i];
      if(arr[sz-d+i] >= limit) arr[sz-d+i] %= md;
    }
  }

  rep(i,sz){
    if(arr[i] >= md) arr[i] %= md;
  }
  rep(i,sz) a[i] = arr[i];
}

template<class S, class T>
ll 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;
  int *A;
  int *D, *E;
  int reduce_size = 0;
  int *reduce_len;
  int *reduce_calc_len;
  mint **reduce_calc;
  ll C;
  int num;
  double chk;

  if(n < d) return a[n];

  chk = (log(2) + log(d) + 2 * log(md)) / log(1004535809);
  num = ceil(chk+1e-5);

  reduce_len = (int*)mem;
  reduce_calc_len = reduce_len + 25;
  reduce_calc = (mint**)(reduce_calc_len+25);
  A = (int*)(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, c, 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;
    gmodconvolutionPreCalc(A, 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 = (int*)(arr+sz);
  E = D + 4*d;
  mem = E + 2*d;

  rep(i,2*d) A[i] = 0;
  A[arr[--sz]] = 1;
  while(sz--){
    gmodconvolution(A, 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;
      gmodconvolutionWithPreCalc(reduce_calc[j], reduce_calc_len[j], D+s-len, len, E, d+len, mem, md, num);
      rep(i,d+len){
        D[st+i+1] += E[i];
        if(D[st+i+1] >= md) D[st+i+1] -= md;
      }
      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] = (A[d+i] + (ll)c[i] * C) % md;
    }
  }

  Kitamasa_g_reduce(A, 2*d, c, d, md, limit, num, reduce_size, reduce_calc, reduce_len, reduce_calc_len, mem);

  C = 0;
  rep(i,d){
    C += (ll)a[i] * A[i];
    if(C>=limit)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_g(N+d-1, aaa, ccc, d, MD, mem);
  writer(res, '\n');


  return 0;
}
0