結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー btkbtk
提出日時 2015-05-23 01:06:43
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 530 ms / 3,000 ms
コード長 3,937 bytes
コンパイル時間 902 ms
コンパイル使用メモリ 98,692 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 05:49:29
合計ジャッジ時間 2,681 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 432 ms
6,812 KB
testcase_01 AC 530 ms
6,944 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)
	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 ans;
	}
};
//テンプレート、デフォルトコンストラクタのオーバーロードを忘れない
#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 temp[70];
LL comb[131] = {0};
LL dp[131] = { 1 };
LL sumc[131] = { 0 };
int sosuu[] = { 2, 3, 5, 7, 11, 13 }, gousei[] = { 4, 6, 8, 9, 10, 12 };
int p, c;
void func1(int val,int now, int n){
	if (n == c){
		for (int i = 0; i < 70; i++)comb[i + val] += temp[i];
		return;
	}
	for (int i = now; i < 6; i++){
		func1(val+gousei[i],i, n + 1);
	}
}
void func2(int val, int now,int n){
	if (n == p){
		temp[val]++;
		return;
	}
	for (int i = now; i < 6; i++){
		func2(val+sosuu[i],i, n + 1);
	}
}
int main(void){
	LL N;
	cin >> N >> p >> c;
	func2(0, 0, 0);
	func1(0, 0, 0);
	vector<X> A(130);
	vector<X> C(130);

	for (int i = 0; i <= 130; i++){
			for (LL j = 1; j <=i; j++){
				dp[i] = (dp[i]+comb[j]*dp[i - j])%MOD;
			}
	}
	for (int i = 0; i < 130; i++){
		A[i] = X(dp[i]);
	}
	for (int i = 1; i <= 130; i++){
		C[130-i] = X(comb[i]);
	}
	sumc[130] = 0;
	for (int i = 129; i >= 0; i--){
		sumc[i] = (sumc[i + 1] + comb[i])%MOD;
	}
	
	Mr<X> mr(A, C, 130, X(1), X(0));
//	cout << sumc[N] << endl;
	LL res = 0;
	for (LL i = 1; i <= 130; i++)
		if (N - i >= 0){
			res = (res + (sumc[i] * mr.calc(N +1- i).val)) % MOD;
			//cout << i << " " << N - i << "  " << sumc[i] << " "<<mr.calc(N +1- i)).val << endl;
		
	}
	cout << res << endl;
	return(0);
}
0