結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー fumofumofunifumofumofuni
提出日時 2021-03-15 15:19:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,559 ms / 3,000 ms
コード長 2,383 bytes
コンパイル時間 2,520 ms
コンパイル使用メモリ 211,556 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-07 03:10:28
合計ジャッジ時間 10,474 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,518 ms
5,248 KB
testcase_01 AC 2,559 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=(n)-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
 ll MOD=1000000007;
 ll MOD9=998244353;
 int inf=1e9+10;
 ll INF=1e18;
 ll dy[8]={1,0,-1,0,1,1,-1,-1};
 ll dx[8]={0,1,0,-1,1,-1,1,-1};
template <typename T> inline bool chmax(T &a, T b) {
  return ((a < b) ? (a = b, true) : (false));
}
template <typename T> inline bool chmin(T &a, T b) {
  return ((a > b) ? (a = b, true) : (false));
}


ll mod=1000000007;//一次元ベクトルの高速化dp
vl matmul(vl &dp, vvl &mt){
    ll m=dp.size();
    vl ret(m,0); 
    rep(i,m)rep(j,m){
        ret[i]+=mt[i][j]*dp[j];
        ret[i]%=mod;
    }
    return ret;
}
vvl update(vvl &mt){
    ll m=mt.size();
    vvl ret(m,vl(m,0));
    rep(i,m)rep(j,m)rep(k,m){
        ret[i][j]+=mt[i][k]*mt[k][j];
        ret[i][j]%=mod;
    }
    return ret;
}
void matpow(vl &dp, vvl &mt, ll k){
    ll m=dp.size();
    while(k){
        if(k&1)dp=matmul(dp,mt);
        mt=update(mt);
        k/=2;
    }
}

vl calc(ll p,vl v){
  ll dp[p+1][100][6];memset(dp,0,sizeof(dp));dp[0][0][0]=1;
  rep(i,p){
    rep(j,80){
      rep(k,6){
        for(int l=k;l<6;l++){
          dp[i+1][j+v[l]][l]+=dp[i][j][k];
        }
      }
    }
  }
  vl ans(100);
  rep(i,100)rep(j,6)ans[i]+=dp[p][i][j];
  return ans;
}
int main(){
  ll n,p,c;cin>>n >>  p >> c;
  vl v1={2,3,5,7,11,13},v2={4,6,8,9,10,12};
  vl x=calc(p,v1),y=calc(c,v2);
  vl to(140);
  rep(i,70){
    rep(j,70){
      if(i+j-1>=0)to[i+j-1]+=x[i]*y[j];
    }
  }
  //rep(i,15)cout << to[i] <<" ";cout << endl;
  vvl mat(140,vl(140));
  vl dp(140);dp[0]=1;
  rep(i,139)mat[i+1][i]=1;
  mat[0]=to;
  matpow(dp,mat,n);
  ll ans=0;
  //rep(i,10)cout << dp[i] <<" ";cout << endl;
  repl(i,1,140){
    ll now=n-i;
    repl(j,1,140){
      if(now+j>=n){
        ans+=dp[i]*to[j-1];
        ans%=MOD;
      }
    }
  }
  cout << ans <<endl;
  //cout << dp[0] <<endl;
}
0