http://agc019.contest.atcoder.jp/tasks/agc019_e
aをS[i]=T[i]=1が成立している数
bをS[i]=1,T[i]=0が成立している数
cをS[i]=T[i]=1を満たす異なる二つのiについてswapを行った回数
としてdpを行う。
b=N-i-a+cが成立するので、O(N^3)で求められます。
1のうち動かせないもの、動かせるものみたいな単純な記号をもとに考察するとだいぶ思いつきやすいかも。
コードを見てみるとわかるように場合分けが大量にあるのでだいぶ筋が悪そうです。
やはり満点解法を取りに行くには、有向グラフの言い換えが思いつかないと厳しいのかなぁ…
int N, M; ll dp[2][MAX_N][MAX_N]; string S, T; void solve() { cin >> S >> T; M = sz(S); if(M > 500) { cout << "0" << "\n"; return; } int a = 0, c = 0; rep(i, 0, M) { if(S[i] == '1') { if(T[i] == '1') c++; else a++; } } N = a + c; dp[0][c][0] = 1; int now = 0, nxt = 1; rep(i, 0, N) { memset(dp[nxt], 0, sizeof(dp[nxt])); rep(a, 0, N + 1) { rep(c, 0, N + 1) { if(a - c * 2 < 0) continue; int b = N - i - a + c; if(b < 0 || !dp[now][a][c]) continue; if(a > 0) ADD(dp[nxt][a - 1][c], dp[now][a][c] * (a - c * 2) % mod * b % mod); if(b > 0) ADD(dp[nxt][a][c], dp[now][a][c] * b % mod * b % mod); if(a - c * 2 > 0) ADD(dp[nxt][a - 1][c], dp[now][a][c] * (a - c * 2) % mod); if(a - c * 2 > 0) ADD(dp[nxt][a - 1][c], dp[now][a][c] * (a - c * 2) % mod * c % mod); if(a - c * 2 > 1) ADD(dp[nxt][a][c + 1], dp[now][a][c] * (a - c * 2) % mod * (a - c * 2 - 1) % mod); if(a - c * 2 > 0) ADD(dp[nxt][a - 1][c], dp[now][a][c] * (a - c * 2) % mod * c % mod); if(a > 1 && c > 0) ADD(dp[nxt][a - 2][c - 1], dp[now][a][c] * c % mod * c % mod); } } now = 1 - now; nxt = 1 - nxt; } cout << dp[now][0][0] << "\n"; }