結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー btkbtk
提出日時 2015-05-23 02:35:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,249 ms / 3,000 ms
コード長 4,607 bytes
コンパイル時間 1,431 ms
コンパイル使用メモリ 98,776 KB
実行使用メモリ 10,572 KB
最終ジャッジ日時 2023-09-20 10:27:17
合計ジャッジ時間 6,117 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,249 ms
10,540 KB
testcase_01 AC 972 ms
10,388 KB
testcase_02 AC 1,047 ms
10,572 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define LL long long
#define all(b) (b).begin(),(b).end()


#define input_init stringstream ss; string strtoken, token; istringstream is
#define input_line  getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit)
#define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num
#define LL long long

const LL mod = (LL) 1e9 + 7;

#define MAX_LOGN 60
template <class T>
struct Mr{
	vector<T> first;
	vector<T> C;
	vector<vector<T>> bin;
	T zero, one;
	int M;
	//n(1,,,2M)をn(1,,,M)に修正、O(M^2)
	void form(vector<T> &n){
		rev(i, M + 1, 2 * M + 1){
			reE(j, 1, M)n[i - j] = (n[i - j] + (C[M - j] * n[i]));
			n[i] = zero;
		}
	}
	//lとrを足し合わせる、O(M^2)
	void add(vector<T> &l, vector<T> &r, vector<T> &ans){
		reE(i, 1, 2 * M)ans[i] = zero;
		reE(i, 1, M)reE(j, 1, M)ans[i + j] = (ans[i + j] + (l[i] * r[j]));
		form(ans);
	}
	//初期化、O(M*MAX_LOGN)
	Mr(const vector<T>& f, const vector<T>& c, int m, T e1, T e0){
		M = m;
		first.reserve(M + 1); C.reserve(M);
		zero = e0, one = e1;
		first.push_back(zero);
		rT(i, M){ first.push_back(f[i]); C.push_back(c[i]); }
		bin.resize(MAX_LOGN);
		rT(i, MAX_LOGN)bin[i].resize(2 * M + 1);
		rE(i, 2 * M)bin[0][i] = zero; bin[0][1] = one;
		reT(i, 1, MAX_LOGN){
			add(bin[i - 1], bin[i - 1], bin[i]);
		}
	}
	//N項目の計算、戻り値がTの形であることに注意、O(M^2*logN)
	vector<T> calc(LL n){
		n--;
		vector<T> tmp, result = bin[0];
		for (int b = 0; n; b++, n >>= 1)
			if (1 & n){ tmp = result; add(tmp, bin[b], result); }
		T ans = zero;
		//reE(i, 1, M)ans = ans + (result[i] * first[i]);
		return result;
	}
};
//テンプレート、デフォルトコンストラクタのオーバーロードを忘れない
#define MOD 1000000007
struct X{
	LL val;
	X(LL  v){ val = v; }
	X(){ val = 0; }
	LL operator=(const X &another){ return val = another.val; }
	LL operator*(const X &another)const{ return (val*another.val) % MOD; }
	LL operator+(const X &another)const{ return (val + another.val) % MOD; }
};

LL comb[1301];
LL temp2[100][1301][6] = { { {1} } };
LL temp1[100][1301][6];
LL dp[2601] = { 1 };
LL sumc[1301] = { 0 };
int sosuu[] = { 2, 3, 5, 7, 11, 13 }, gousei[] = { 4, 6, 8, 9, 10, 12 };
int p, c;

void func1(int n){
	if (n == c){
		for (int i = 0; i < 1300; i++){
			for (int j = 0; j < 6; j++)
				comb[i] = (comb[i] + temp1[n][i][j]) % MOD;
		}
		return;
	}
	for (int j = 0; j < 6; j++)
		for (int i = gousei[j]; i < 1300; i++){
			for (int k = 0; k <= j; k++)
				temp1[n + 1][i][j] = (temp1[n + 1][i][j] + temp1[n][i - gousei[j]][k]) % MOD;
		}
	func1(n + 1);
}
void func2(int n){
	if (n == p){
		for (int i = 0; i < 1300; i++){
			for (int j = 0; j < 6; j++)
				temp1[0][i][0] = (temp1[0][i][0] + temp2[n][i][j]) % MOD;
		}
		func1(0);
		return;
	}
		for (int j = 0; j < 6; j++)
			for (int i = sosuu[j]; i < 1300; i++){
				for (int k = 0; k <= j; k++)
					temp2[n + 1][i][j] = (temp2[n + 1][i][j] + temp2[n][i - sosuu[j]][k]) % MOD;
			}
		func2(n + 1);
}

vector<X> A(1300), C(1300);
int main(void){
	LL N;
	cin >> N >> p >> c;
	func2(0);

	for (int i = 0; i <= 2600; i++){
		for (LL j = 1; j <= min(i,1300); j++){
			dp[i] = (dp[i] + comb[j] * dp[i - j]) % MOD;
		}
	}
	for (int i = 0; i < 1300; i++){
		A[i] = X(dp[i]);
	}
	for (int i = 1; i <= 1300; i++){
		C[1300 - i] = X(comb[i]);
	}
	sumc[1300] = 0;
	for (int i = 1299; i >= 0; i--){
		sumc[i] = (sumc[i + 1] + comb[i]) % MOD;
	}

	
	LL res = 0;
	if (N < 1400){
		for (LL i = 0; i < min(N,1300ll); i++)
		{
			res = (res + dp[i] * sumc[min(N,1300ll) - i])%MOD;
		}

	}
	else{
		Mr<X> mr(A, C, 1300, X(1), X(0));
		
		auto cc = mr.calc(N + 1 - 1300);
		for (LL i = 0; i < 1300; i++)
		if(sumc[1300-i]){
			LL x = 0;
			for (int j = 0; j < 1300; j++){
				x = (x + dp[i + j] * cc[j + 1].val) % MOD;

			}
			res = (res + x*sumc[1300 - i])%MOD;
			//cout << x <<" "<<sumc[1300-i]<< endl;
		}
		
	}
	cout << res << endl;
	return(0);
}
0