結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
コンテスト
ユーザー ゴリポン先生
提出日時 2026-03-24 10:44:21
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 939 ms / 3,000 ms
コード長 2,933 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,619 ms
コンパイル使用メモリ 193,536 KB
実行使用メモリ 45,824 KB
最終ジャッジ日時 2026-03-24 10:44:32
合計ジャッジ時間 6,854 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/checkedint.d(814): Warning: cannot inline function `core.checkedint.mulu!().mulu`
ulong mulu()(ulong x, uint y, ref bool overflow)
      ^

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/06/03/0900 より
// 組み合わせ、行列累乗
import std;

long N;
int P, C;

immutable MOD = 10L ^^ 9 + 7;
// https://ei1333.github.io/library/math/matrix/matrix.hpp より
struct Matrix(T) {
	T[][] A;
	alias A this;
	// コンストラクタ
	this(size_t n, size_t m)
	{
		A = new T[][](n, m);
	}
	this(size_t n)
	{
		A = new T[][](n, n);
	}
	// 行数
	size_t height() const
	{
		return A.length;
	}
	// 列数
	size_t width() const
	{
		return A[0].length;
	}
	// 単位行列
	static Matrix I(size_t n)
	{
		auto mat = Matrix(n);
		foreach (i; 0 .. n) mat[i][i] = 1;
		return mat;
	}
	/*
	 * 演算代入演算子
	 */
	// 加減算
	Matrix opOpAssign(string op)(Matrix B)
		if (op == "+" || op == "-")
	{
		size_t n = height(), m = width();
		assert(n == B.height() && m == B.width());
		foreach (i; 0 .. n)
			foreach (j; 0 .. m) mixin("A[i][j] " ~ op ~ "= B[i][j]");
		foreach (i; 0 .. n)
			foreach (j; 0 .. m)
				A[i][j] = (A[i][j] + MOD) %MOD;
		return this;
	}
	// 掛け算
	Matrix opOpAssign(string op : "*")(Matrix B)
	{
		size_t n = height(), m = B.width(), p = width();
		assert(p == B.height());
		auto C = new T[][](n, m);
		foreach (i; 0 .. n)
			foreach (j; 0 .. m)
				foreach (k; 0 .. p)
					C[i][j] += (A[i][k] * B[k][j]) % MOD;
		foreach (i; 0 .. n)
			foreach (j; 0 .. m)
				C[i][j] = (C[i][j] + MOD) %MOD;
		swap(A, C);
		return this;
	}
	// 累乗
	Matrix opOpAssign(string op : "^^")(long k)
	{
		auto B = I(height());
		while (k > 0) {
			if (k & 1) B *= this;
			this *= this;
			k >>= 1;
		}
		swap(A, B.A);
		return this;
	}
	/*
	 * 二項演算子
	 */
	Matrix opBinary(string op)(Matrix B)
		if (op == "+" || op == "-" || op == "*")
	{
		auto ret = this;
		mixin("return ret " ~ op ~ "= B;");
	}
	Matrix opBinary(string op : "^^")(long k)
	{
		auto ret = this;
		return ret ^^= k;
	}
	// 標準出力
	string toString() const
	{
		return format("%s", A);
	}
	// 行列式
	T determinant()
	{
		Matrix B = this;
		assert(width() == height());
		T ret = 1;
		
		return ret;
	}
}

void main()
{
	// 入力
	readln.chomp.formattedRead("%d %d %d", N, P, C);
	// 答えの計算
	auto A = [2, 3, 5, 7, 11, 13], B = [4, 6, 8, 9, 10, 12];
	auto dp = new long[][][](2, 400, 4000);
	dp[0][0][0] = dp[1][0][0] = 1;

	foreach (a; A)
		foreach (y; 0 .. P)
			foreach (i; 0 .. y * 13 + 1)
				if (dp[0][y][i])
					dp[0][y + 1][i + a] += dp[0][y][i];
	foreach (b; B)
		foreach (y; 0 .. C)
			foreach (i; 0 .. y * 12 + 1)
				if (dp[1][y][i])
					dp[1][y + 1][i + b] += dp[1][y][i];
	auto single = new long[](8010);
	foreach (x; 0 .. 651)
		foreach (y; 0 .. 601)
			single[x + y] += dp[0][P][x] * dp[1][C][y];

	int M = P * 13 + C * 12;

	auto mm = Matrix!long(130);
	foreach (i; 0 .. M - 1)
		mm[i][i + 1] = 1;
	foreach (i; 1 .. M + 1)
		mm[M - 1][M - i] = single[i];

	auto m2 = mm ^^ (N + M - 1);
	// 答えの出力
	writeln(m2[0].sum % MOD);
}
0