結果
問題 | No.215 素数サイコロと合成数サイコロ (3-Hard) |
ユーザー |
![]() |
提出日時 | 2024-11-06 00:38:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,615 bytes |
コンパイル時間 | 5,277 ms |
コンパイル使用メモリ | 276,384 KB |
最終ジャッジ日時 | 2025-02-25 02:23:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | MLE * 2 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint1000000007;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001template <class T>vector<T> convolution_mint(vector<T> a,vector<T> b){static constexpr unsigned long long M0 = 998244353;static constexpr unsigned long long M1 = 754974721;static constexpr unsigned long long M2 = 469762049;vector<long long> aa(a.size()),bb(b.size());rep(i,a.size())aa[i] = a[i].val();rep(i,b.size())bb[i] = b[i].val();auto c0 = convolution<M0>(aa,bb);auto c1 = convolution<M1>(aa,bb);auto c2 = convolution<M2>(aa,bb);vector<mint> ret(c0.size());rep(i,c0.size()){ret[i] += c0[i];{long long cur = c0[i];cur %= M1;cur = c1[i]-cur;if(cur<0)cur += M1;cur *= 416537774;cur %= M1;mint m = M0;ret[i] += m*cur;cur *= M0;cur += c0[i];cur %= M2;cur = c2[i] - cur;if(cur<0)cur += M2;cur *= 429847628;cur %= M2;m *= M1;ret[i] += m * cur;}}return ret;}vector<mint> mul(vector<mint> a,vector<mint> b){return convolution_mint(a,b);}mint Bostan_Mori(vector<mint> a,vector<mint> c,long long n){while(a.size()>=c.size())c.push_back(0);while(n!=0){auto cinv = c;for(int i=1;i<cinv.size();i+=2)cinv[i] *= -1;a = mul(a,cinv);c = mul(c,cinv);{vector<mint> na;for(int i=(n&1LL);i<a.size();i+=2)na.push_back(a[i]);swap(a,na);}{vector<mint> nc;for(int i=0;i<c.size();i+=2)nc.push_back(c[i]);swap(c,nc);}n>>=1;}return a[0];}int main(){long long n,p,c;cin>>n>>p>>c;vector<int> x= {2,3,5,7,11,13},y = {4,6,8,9,10,12};vector dp(p+1,vector(6,vector<mint>(13*p+1)));dp[0][0][0] = 1;rep(i,p+1){rep(j,6){rep(k,13*p+1){if(dp[i][j][k].val()==0)continue;if(j!=5)dp[i][j+1][k] += dp[i][j][k];if(i!=p)dp[i+1][j][k+x[j]] += dp[i][j][k];}}}{vector ndp(c+1,vector(6,vector<mint>(13*p+12*c+1)));rep(i,13*p+1){ndp[0][0][i] = dp[p][5][i];}dp = ndp;}rep(i,c+1){rep(j,6){rep(k,13*p+12*c+1){if(dp[i][j][k].val()==0)continue;if(j!=5)dp[i][j+1][k] += dp[i][j][k];if(i!=c)dp[i+1][j][k+y[j]] += dp[i][j][k];}}}vector<mint> C(13*p+12*c+1,0);rep(i,13*p+12*c+1)C[i] = dp[c][5][i];vector<mint> a(C.size(),0);for(int i=C.size()-1;i>=1;i--){a[i] = C[i];if(i!=C.size()-1)a[i] += a[i+1];}rep(i,C.size())C[i] *= -1;C[0] = 1;cout<<Bostan_Mori(a,C,n).val()<<endl;return 0;}