結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー snrnsidysnrnsidy
提出日時 2023-04-17 10:57:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 680 ms / 3,000 ms
コード長 4,705 bytes
コンパイル時間 3,494 ms
コンパイル使用メモリ 366,248 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 12:45:45
合計ジャッジ時間 5,080 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")	
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using poly = vector<ll>;

const long long int MOD = 1e9 + 7;
long long int dp[2][6][71];
long long int c[141];
vector <int> a = {2,3,5,7,11,13};
vector <int> b = {4,6,8,9,10,12};
long long int n,p,q;
vector <int> v;
long long int dp2[141];


int Mod(ll x){
    return (x %= MOD) < 0 ? x + MOD : x;
}

poly Mul(const poly &a, const poly &b){
    poly ret(a.size() + b.size() - 1);
    for(int i=0; i<a.size(); i++) for(int j=0; j<b.size(); j++) {
        ret[i+j] = (ret[i+j] + a[i] * b[j]) % MOD;
    }
    return ret;
}

poly Div(const poly &a, const poly &b){
    poly ret(a.begin(),a.end());
    for(int i=ret.size()-1; i>=b.size()-1; i--) for(int j=0; j<b.size(); j++) {
        ret[i+j-b.size()+1] = Mod(ret[i+j-b.size()+1] - ret[i] * b[j]);
    }
    ret.resize(b.size()-1);
    return ret;
}

/// kitamasa: A_{n} = \sum c_{i}A_{n-i} = \sum d_{i}A_{i}
/// given A, c, n, get d, A_{n} in O(K^2 \log N)
ll kitamasa(poly c, poly a, ll n){
    poly d = {1}; // result
    poly xn = {0, 1}; // shift = x^1, x^2, x^4, ...
    poly f(c.size()+1); // f(x) = x^K - \sum c_{i}x^{i}
    f.back() = 1;
    for(int i=0; i<c.size(); i++) f[i] = Mod(-c[i]);
    while(n){
        if(n & 1) d = Div(Mul(d, xn), f);
        n >>= 1; xn = Div(Mul(xn, xn), f);
    }

    ll ret = 0;
    for(int i=0; i<a.size(); i++) ret = Mod(ret + a[i] * d[i]);
    return ret;
}

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n >> p >> q;

	int m = p*a[5] + q*b[5];

	dp[0][0][0] = 1;
	dp[1][0][0] = 1;

	for(int i=0;i<a.size();i++)
	{
		for(int j=p-1;j>=0;j--)
		{
			for(int k=0;k<=p*a[5];k++)
			{
				if(dp[0][j][k]==0) continue;
				for(int l=j+1;l<=p;l++)
				{
					if(k + (l-j)*a[i] > p*a[5]) break;
					dp[0][l][k + (l-j)*a[i]] += dp[0][j][k];
					dp[0][l][k + (l-j)*a[i]]%=MOD;
				}
			}
		}
	}

	for(int i=0;i<b.size();i++)
	{
		for(int j=q-1;j>=0;j--)
		{
			for(int k=0;k<=q*b[5];k++)
			{
				if(dp[1][j][k]==0) continue;
				for(int l=j+1;l<=q;l++)
				{
					if(k + (l-j)*b[i] > q*b[5]) break;
					dp[1][l][k + (l-j)*b[i]] += dp[1][j][k];
					dp[1][l][k + (l-j)*b[i]]%=MOD;
				}
			}
		}
	}

	for(int i=0;i<=p*a[5];i++)
	{
		for(int j=0;j<=q*b[5];j++)
		{
			if(i+j > m) continue;
			c[i+j] += ((dp[0][p][i]*dp[1][q][j])%MOD);
			c[i+j]%=MOD;
		}
	}

	dp2[0] = 1;

	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(i+j > m) break;
			dp2[i+j] += ((dp2[i]*c[j])%MOD);
			dp2[i+j]%=MOD;
		}
	}

	poly A,C;

	for(int i=0;i<=m;i++)
	{
		A.push_back(dp2[i]);
	}

	for(int i=m;i>0;i--)
	{
		C.push_back(c[i]);
	}

	long long int res = 0;

	long long int L = n - m;
	if(L < 0) L = 0;
	long long int R = n - 1;
	for(long long int i=L;i<=R;i++)
	{
		long long int val = kitamasa(C,A,i);
		for(int j=0;j<=m;j++)
		{
			if(i+j >= n)
			{
				res += ((val*c[j])%MOD);
				res%=MOD;
			}
		}
	}

	cout << res << '\n';

	return 0;
}
0