結果
問題 |
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 |
ソースコード
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]); }