結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー btkbtk
提出日時 2015-05-23 11:14:44
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 12 ms / 3,000 ms
コード長 4,312 bytes
コンパイル時間 911 ms
コンパイル使用メモリ 87,900 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-20 10:39:30
合計ジャッジ時間 1,272 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#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 LL long long
#define BUFFSIZE (long long)130

#define MAX_LOGN 60
template <class T>
class Mr{
public:
	vector<T> first;
	vector<T> C;
	vector<vector<T>> bin;
	list<int> usefulL;
	list<int> usefulR;
	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)
				if(n[i].val){
			reE(j, 1, M)n[i - j] = (n[i - j] + (C[M - j] * n[i]));
			n[i] = zero;
		}
	}
	//lとrを足し合わせる、O(M^2)
	inline void add(vector<T> &l, vector<T> &r, vector<T> &ans){
		usefulL.clear();
		usefulR.clear();
		reE(i,1,M){
			if(l[i].val)usefulL.push_back(i);
			if(r[i].val)usefulR.push_back(i);
		}
		reE(i, 1, 2 * M)ans[i] = zero;
		for(auto &i:usefulL)for(auto &j:usefulR)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); }
		//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[BUFFSIZE+1];
LL temp[301][BUFFSIZE+1][6];
LL dp[2*BUFFSIZE+1] = { 1 };
LL sumc[BUFFSIZE+1] = { 0 };
int sosuu[] = { 2, 3, 5, 7, 11, 13 }, gousei[] = { 4, 6, 8, 9, 10, 12 };
int p, c;


vector<X> C(BUFFSIZE+1);
int main(void){
	LL N;
	cin >> N >> p >> c;
	//combの計算
	temp[0][0][0]=1;
	for(int n=0;n<p;n++)
		for (int j = 0; j < 6; j++)
				for (int i = sosuu[j]; i <= BUFFSIZE; i++)
					for (int k = 0; k <= j; k++)
						temp[n + 1][i][j] = (temp[n + 1][i][j] + temp[n][i - sosuu[j]][k]) % MOD;
	if(p)for (int i = 0; i <= BUFFSIZE; i++){
		temp[0][i][0]=0;
				for (int j = 0; j < 6; j++)
					temp[0][i][0] = (temp[0][i][0] + temp[p][i][j]) % MOD;
	}
	for(int i=1;i<=p;i++)
		for(int j=0;j<=BUFFSIZE;j++)
			for(int k=0;k<6;k++)
				temp[i][j][k]=0;
	for(int n=0;n<c;n++)
		for (int j = 0; j < 6; j++)
			for (int i = gousei[j]; i <= BUFFSIZE; i++)
				for (int k = 0; k <= j; k++)
					temp[n + 1][i][j] = (temp[n + 1][i][j] + temp[n][i - gousei[j]][k]) % MOD;
	for (int i = 0; i <= BUFFSIZE; i++)
		for (int j = 0; j < 6; j++)
			comb[i] = (comb[i] + temp[c][i][j]) % MOD;
	//漸化式の初項部分
	for (LL i = 0; i <= 2*BUFFSIZE; i++){
		for (LL j = 1; j <= min(i,BUFFSIZE); j++){
			dp[i] = (dp[i] + comb[j] * dp[i - j]) % MOD;
		}
	}
	//漸化式の係数部分
	for (int i = 1; i <= BUFFSIZE; i++){
		C[BUFFSIZE - i] = X(comb[i]);
	}
	for (int i = BUFFSIZE-1; i >= 0; i--){
		sumc[i] = (sumc[i + 1] + comb[i]) % MOD;
	}
	LL res = 0;
	if (N < BUFFSIZE+100){
		for (LL i = 0; i < min(N,BUFFSIZE); i++)
			res = (res + dp[i] * sumc[min(N,BUFFSIZE) - i])%MOD;
	}
	else{
		Mr<X> mr(C, C, BUFFSIZE, X(1), X(0));

		auto cc = mr.calc(N + 1 - BUFFSIZE);
		for (LL i = 0; i < BUFFSIZE; i++)
		if(sumc[BUFFSIZE-i]){
			LL x = 0;
			for (int j = 0; j < BUFFSIZE; j++)
				x = (x + dp[i + j] * cc[j + 1].val) % MOD;
			res = (res + x*sumc[BUFFSIZE - i])%MOD;
		}
	}
	cout << res << endl;
	return(0);
}
0