結果

問題 No.93 ペガサス
コンテスト
ユーザー ゴリポン先生
提出日時 2025-07-27 22:55:02
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 39 ms / 5,000 ms
コード長 1,671 bytes
コンパイル時間 3,513 ms
コンパイル使用メモリ 161,836 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-27 22:55:07
合計ジャッジ時間 4,879 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://kmjp.hatenablog.jp/entry/2014/12/08/1000 より
// 動的計画法 Nクイーン 2次元グリッド
import std;

immutable MOD = 1_000_000_007L;
void add(ref long a, long b) { a = (a + b) % MOD; }
// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}

void main()
{
	// 入力
	long N = readln.chomp.to!long;
	// 答えの計算
	if (N == 1 || N == 2) {
		writeln(N);
		return;
	}
	auto dp = new long[][][][](2, N + 1, 2, 2);
	dp[0][0][0][0] = 2;
	foreach (i; 2 .. N) {
		int cur = i % 2, tar = cur ^ 1;
		fill(dp[tar], 0);
		foreach (x; 0 .. i - 1) {
			long v;
			if (x >= 2) {
				v = dp[cur][x][1][1];
				if (v) {
					dp[tar][x][1][1].add(v);
					dp[tar][x - 1][0][0].add(v);
					dp[tar][x - 1][1][0].add(v * (x - 2));
					dp[tar][x + 1][1][1].add(v);
					dp[tar][x][1][0].add(v * (i + 1 - x - 1));
				}
			}
			if (x >= 1) {
				v = dp[cur][x][0][1];
				if (v) {
					dp[tar][x - 1][0][0].add(v);
					dp[tar][x - 1][1][0].add(v * (x - 1));
					dp[tar][x + 1][1][1].add(v * 2);
					dp[tar][x][1][0].add(v * (i + 1 - x - 2));
				}
				v = dp[cur][x][1][0];
				if (v) {
					dp[tar][x][0][1].add(v);
					dp[tar][x - 1][0][0].add(v * (x - 1));
					dp[tar][x + 1][0][1].add(v);
					dp[tar][x][0][0].add(v * (i + 1 - x - 1));
				}
			}
			v = dp[cur][x][0][0];
			if (v) {
				dp[tar][x + 1][0][1].add(v * 2);
				if (x > 0) dp[tar][x - 1][0][0].add(x * v);
				dp[tar][x][0][0].add(v * (i + 1 - x - 2));
			}
		}
	}
	// 答えの出力
	writeln(dp[N % 2][0][0][0]);
}
0