コード
import java.util.Arrays;
public class AdjacentSwaps {
private final int MOD = (int) 1e9 + 7;
private long[][] dp, nCm;
private int[] p;
public int theCount(int[] permutation) {
int N = permutation.length;
this.p = permutation;
nCm = new long[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
nCm[i][j] = (j == 0 || j == i) ? 1
: (nCm[i - 1][j - 1] + nCm[i - 1][j]) % MOD;
}
}
dp = new long[N][N];
for (int i = 0; i < permutation.length; i++) {
Arrays.fill(dp[i], -1);
}
return dp(0, N - 1);
}
private int dp(int left, int right) {
if (right == left) {
return 1;
}
if (dp[left][right] >= 0) {
return (int) dp[left][right];
}
dp[left][right] = 0;
outer: for (int i = left; i < right; i++) {
int[] pLeftRight = Arrays.copyOfRange(p, left, right + 1);
int[] pHalfLeft = Arrays.copyOfRange(p, left, i + 1);
Arrays.sort(pLeftRight);
Arrays.sort(pHalfLeft);
for (int j = left; j <= i - 1; j++) {
if (pLeftRight[j - left] != pHalfLeft[j - left]) {
continue outer;
}
}
if (pLeftRight[i + 1 - left] != pHalfLeft[i - left]) {
continue outer;
}
long pattern = ((long) dp(left, i) * dp(i + 1, right)) % MOD;
pattern = (pattern * nCm[right - left - 1][i - left]) % MOD;
dp[left][right] = (dp[left][right] + pattern) % MOD;
}
return (int) dp[left][right];
}
}