結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー beetbeet
提出日時 2020-02-21 17:31:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,751 bytes
コンパイル時間 2,411 ms
コンパイル使用メモリ 211,588 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-17 06:47:54
合計ジャッジ時間 2,897 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T>
struct Kitamasa{
  using VT = vector<T>;
  using F = function<T(T,T)>;
  VT c;
  vector<VT> rs;
  int m;
  F add;
  F mul;
  T d0,d1;
  
  Kitamasa(const VT &C,F add,F mul,T d0,T d1)
    :c(C),rs(1),m(c.size()),add(add),mul(mul),d0(d0),d1(d1){
    rs[0].assign(2*m+1,d0);
    rs[0][1]=d1;
  }

  VT merge(const VT &x,const VT &y){
    VT z(2*m+1,d0);
    for(int i=1;i<=m;i++)
      for(int j=1;j<=m;j++)
        z[i+j]=add(z[i+j],mul(x[i],y[j]));
    
    for(int i=2*m;i>m;z[i--]=d0)
      for(int j=1;j<=m;j++)
        z[i-j]=add(z[i-j],mul(c[m-j],z[i]));
    
    return z;
  }

  T calc(long long n){
    static VT res(rs[0]);
    for(int i=0;n;i++,n>>=1){
      if(i>=(int)rs.size())
        rs.emplace_back(merge(rs[i-1],rs[i-1]));
      if(~n&1) continue;
      res=merge(res,rs[i]);
    }
    T ans=d0;
    for(int i=1;i<=m;i++) ans=add(ans,mul(res[i],c[m-(i+1)]));
    return ans;
  }
  
};


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  Mint inv(){return pow(MOD-2);}
  
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
  
  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

};
//INSERT ABOVE HERE
signed main(){
  int n,p,c;
  cin>>n>>p>>c;

  int d=13*p+12*c;
  
  using M = Mint<int>;
  
  vector<vector<M> > dp(14,vector<M>(d+1,0));
  vector<M> dp1(d+1,0),dp2(d+1,0);
  
  dp[0][0]=M(1);
  for(int i=0;i<p;i++){
    vector<int> v({2,3,5,7,11,13});
    for(int k=13;k>=0;k--){
      for(int j=d;j>=0;j--){
        for(int x:v)
          if(j+x<=d&&k<=x) dp[x][j+x]+=dp[k][j];
        dp[k][j]=M(0);
      }
    }
  }
  {    
    vector<int> v({0,2,3,5,7,11,13});
    for(int j=0;j<=d;j++)
      for(int x:v) dp1[j]+=dp[x][j];
  }
  
  dp=vector<vector<M> >(14,vector<M>(d+1,0));
  dp[0][0]=M(1);
  for(int i=0;i<c;i++){
    vector<int> v({4,6,8,9,10,12});
    for(int k=13;k>=0;k--){
      for(int j=d;j>=0;j--){
        for(int x:v)
          if(j+x<=d&&k<=x) dp[x][j+x]+=dp[k][j];
        dp[k][j]=M(0);
      }
    }
  }
  {    
    vector<int> v({0,4,6,8,9,10,12});
    for(int j=0;j<=d;j++)
      for(int x:v) dp2[j]+=dp[x][j];
  }
  
  //for(int j=0;j<=d;j++) cout<<j<<":"<<dp1[j].v<<" "<<dp2[j].v<<endl;
  
  vector<M> way(d+1,0);
  for(int i=0;i<=d;i++)
    for(int j=0;j<=d;j++)
      if(i+j<=d) way[i+j]+=dp1[i]*dp2[j];
  reverse(way.begin(),way.end());
  //for(int j=0;j<d;j++) cout<<d-j<<":"<<way[j].v<<endl;
  
  auto add=[](M a,M b){return a+b;};
  auto mul=[](M a,M b){return a*b;};

  M d1(1),d0(0);
  Kitamasa<M> ki(way,add,mul,d0,d1);

  M ans(0);
  ans+=ki.calc(n-1);
  cout<<ans.v<<endl;
  
  for(int i=1;i<d;i++) ans+=ki.calc(1);
  //cout<<n<<":"<<ki.calc(n-1).v<<endl;
  //for(int i=1;i<d;i++) cout<<n+i<<":"<<ki.calc(1).v<<endl;

  cout<<ans.v<<endl;
  return 0;
}
0