結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー chocoruskchocorusk
提出日時 2020-02-24 14:47:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 512 ms / 3,000 ms
コード長 3,420 bytes
コンパイル時間 1,279 ms
コンパイル使用メモリ 119,972 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 04:54:35
合計ジャッジ時間 3,452 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
vector<ll> mul(vector<ll> a, vector<ll> b, vector<ll> c){
    int m=(int)c.size()-1;
    vector<ll> d(a.size()+b.size()-1);
    for(int i=0; i<a.size(); i++){
        for(int j=0; j<b.size(); j++){
            (d[i+j]+=a[i]*b[j])%=MOD;
        }
    }
    while(d.size()>m){
        if(d.back()==0){
            d.pop_back(); continue;
        }
        for(int i=0; i<m; i++){
            (d[(int)d.size()-1-(m-i)]+=(MOD-c[i])*d.back())%=MOD;
        }
        d.pop_back();
    }
    return d;
}
vector<ll> pow(ll n, vector<ll> c){
    int m=(int)c.size()-1;
    vector<ll> v{0, 1}, ret{1};
    while(n){
        if(n&1){
            ret=mul(ret, v, c);
        }
        v=mul(v, v, c);
        n>>=1;
    }
    return ret;
}
ll kitamasa(ll n, vector<ll> c, vector<ll> a){//a[n]=c[k-1]a[n-1]+...+c[0]a[n-k]
    int m=c.size();
    for(int i=0; i<m; i++){
        if(c[i]) c[i]=MOD-c[i];
    }
    c.push_back(1);
    vector<ll> v=pow(n, c);
    ll ret=0;
    for(int i=0; i<m; i++) (ret+=a[i]*v[i])%=MOD;
    return ret;
}
int main()
{
    ll n;
    int p, c;
    cin>>n>>p>>c;
    ll dp1[51][651]={}, dp2[51][601]={};
    dp1[0][0]=1, dp2[0][0]=1;
    int a[6]={2, 3, 5, 7, 11, 13}, b[6]={4, 6, 8, 9, 10, 12};
    for(int i=0; i<6; i++){
        for(int j=0; j<p; j++){
            for(int k=0; k<=13*p-a[i]; k++){
                (dp1[j+1][k+a[i]]+=dp1[j][k])%=MOD;
            }
        }
    }
    for(int i=0; i<6; i++){
        for(int j=0; j<c; j++){
            for(int k=0; k<=12*c-b[i]; k++){
                (dp2[j+1][k+b[i]]+=dp2[j][k])%=MOD;
            }
        }
    }
    ll dp[1251]={};
    for(int i=0; i<=13*p; i++){
        for(int j=0; j<=12*c; j++) (dp[i+j]+=dp1[p][i]*dp2[c][j])%=MOD;
    }
    ll dp0[1251]={};
    dp0[0]=1;
    for(int i=1; i<=13*p+12*c; i++){
        for(int j=1; j<=i; j++){
            (dp0[i]+=dp0[i-j]*dp[j])%=MOD;
        }
    }
    if(n<=13*p+12*c){
        ll ans=0;
        for(int i=0; i<n; i++){
            for(int j=n-i; j<=13*p+12*c; j++){
                (ans+=dp0[i]*dp[j])%=MOD;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    vector<ll> vc(13*p+12*c+1), va(13*p+12*c);
    for(int i=1; i<=13*p+12*c; i++) vc[13*p+12*c-i]=(MOD-dp[i])%MOD, va[i-1]=dp0[i-1];
    vc[13*p+12*c]=1;
    vector<ll> vp=pow(n-(13*p+12*c), vc);
    ll ans=0;
    ll e[1251]={};
    for(int i=0; i<13*p+12*c; i++){
        for(int j=0; j<13*p+12*c; j++){
            (e[i]+=va[j]*vp[j])%=MOD;
        }
        vector<ll> tmp(13*p+12*c);
        for(int j=0; j<13*p+12*c-1; j++) tmp[j+1]=vp[j];
        for(int j=0; j<13*p+12*c; j++){
            (tmp[j]+=(MOD-vc[j])*vp.back())%=MOD;
        }
        vp=tmp;
    }
    for(int i=0; i<13*p+12*c; i++){
        for(int j=13*p+12*c-i; j<=13*p+12*c; j++){
            (ans+=dp[j]*e[i])%=MOD;
        }
    }
    cout<<ans<<endl;
    return 0;
}
0