結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
コンテスト
ユーザー sugim48
提出日時 2015-05-22 23:06:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,523 bytes
コンパイル時間 1,007 ms
コンパイル使用メモリ 106,928 KB
実行使用メモリ 17,720 KB
最終ジャッジ日時 2024-07-06 05:27:32
合計ジャッジ時間 9,407 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <fstream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

vector< vector<ll> > matmul(vector< vector<ll> >& A, vector< vector<ll> >& B) {
	int n = A.size();
	vector< vector<ll> > C(n, vector<ll>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
	return C;
}

vector< vector<ll> > matpow(vector< vector<ll> > A, ll x) {
	int n = A.size();
	vector< vector<ll> > B(n, vector<ll>(n));
	for (int i = 0; i < n; i++) B[i][i] = 1;
	while (x > 0) {
		if (x % 2) B = matmul(B, A);
		x /= 2;
		A = matmul(A, A);
	}
	return B;
}

int a[6] = {2, 3, 5, 7, 11, 13};
int b[6] = {4, 6, 8, 9, 10, 12};

int main() {
	ll N; int P, C;
	cin >> N >> P >> C;
	vector<int> c(152), d(152), e(152);
	string s = string(P, 'o') + "|||||";
	string t = string(C, 'o') + "|||||";
	do {
		int sum = 0;
		vector<int> v;
		v.push_back(0);
		for (int i = 0; i < s.length(); i++)
			if (s[i] == '|')
				v.push_back(i + 1);
		v.push_back(P + 6);
		for (int i = 0; i + 1 < v.size(); i++)
			sum += (v[i + 1] - v[i] - 1) * a[i];
		c[sum]++;
	} while (next_permutation(s.begin(), s.end()));
	do {
		int sum = 0;
		vector<int> w;
		w.push_back(0);
		for (int i = 0; i < t.length(); i++)
			if (t[i] == '|')
				w.push_back(i + 1);
		w.push_back(C + 6);
		for (int i = 0; i + 1 < w.size(); i++)
			sum += (w[i + 1] - w[i] - 1) * b[i];
		d[sum]++;
	} while (next_permutation(t.begin(), t.end()));
	for (int i = 0; i < 152; i++)
		for (int j = 0; j < 152; j++)
			if (i + j < 152)
				e[i + j] += c[i] * d[j];
	vector<vector<ll> > A(151, vector<ll>(151));
	for (int i = 0; i < 150; i++)
		A[i][i + 1] = 1;
	for (int i = 0; i <= 150; i++)
		A[150][i] = e[151 - i];
	A = matpow(A, N - 1);
	int ans = 0;
	for (int i = 0; i <= 150; i++)
		for (int j = 0; j <= 150; j++)
			if (i + j > 150)
				ans = (ans + A[i][150] * e[j]) % MOD;
	cout << ans << endl;
}
0