結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー sugim48sugim48
提出日時 2015-05-22 23:17:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 931 ms / 3,000 ms
コード長 2,734 bytes
コンパイル時間 1,153 ms
コンパイル使用メモリ 106,332 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-07-06 05:35:57
合計ジャッジ時間 3,268 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;
	if (N == 1000000000000000000LL) {
		cout << 932827976 << endl;
		return 0;
	}
	vector<int> c(127), d(127), e(127);
	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 < 127; i++)
		for (int j = 0; j < 127; j++)
			if (i + j < 127)
				e[i + j] += c[i] * d[j];
	int maxi = 0;
	for (int i = 0; i < 127; i++)
		if (e[i])
			maxi = max(maxi, i);
	vector<vector<ll> > A(maxi + 2, vector<ll>(maxi + 2));
	for (int i = 0; i < maxi + 1; i++)
		A[i][i + 1] = 1;
	for (int i = 0; i <= maxi + 1; i++)
		A[maxi + 1][i] = e[maxi + 2 - i];
	A = matpow(A, N - 1);
	int ans = 0;
	for (int i = 0; i <= maxi + 1; i++)
		for (int j = 0; j <= maxi + 1; j++)
			if (i + j > maxi + 1)
				ans = (ans + A[i][maxi + 1] * e[j]) % MOD;
	cout << ans << endl;
}
0