TopCoder SRM 590: FoxAndShogi
各列の状態はそれぞれ独立しているので、各列ごとに状態数を求めてそれらを掛け合わせる。
列ごとの状態数については、上からコマを置いていって、「何番目のコマか」と「コマを置ける一番上の場所」で DP する。
public class FoxAndShogi { const int mod = 1000000007; public int count(char[] s) { int n = s.Length; var symbols = Enumerable.Range(0, n).Where(i => s[i] != '.').ToArray(); if (symbols.Count() == 0) return 1; var dp = new int[n + 1, symbols.Length + 1]; for (int i = 0; i < symbols.Length; i++) { char c = s[symbols[i]]; for (int j = 0; j < n; j++) { if (c == 'D' && j < symbols[i]) continue; if (c == 'U' && j > symbols[i]) continue; if (i == 0) dp[j, i] = 1; else { for (int k = 0; k < j; k++) { dp[j, i] += dp[k, i - 1]; dp[j, i] %= mod; } } } } long ans = 0; for (int i = 0; i < n; i++) { ans += dp[i, symbols.Length - 1]; ans %= mod; } return (int)ans; } public int differentOutcomes(string[] board) { int n = board.Length; var array = board.Select(s => s.ToCharArray()).ToArray(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { array[i][j] = board[j][i]; } } long ans = 1; for (int i = 0; i < n; i++) { ans = (ans * count(array[i])) % mod; } return (int)ans; } }