括弧内は本番で気がつくことのなかった反省点．反省点しかないとかいわない．
0..N-1の整数で表される数列pがある．
すべての整数k(0<=k<N-1)について，p[k]とp[k+1]を入れ替える操作を1回ずつ行い，pを昇順にソートしたい．</ppp>
このとき，並べ替える方法は何通りあるか．
dp[i][j]をi番目からj番目までの要素を昇順に並べ替える方法の数としてDP．(DPの方針を間違えたので，重複が削除できなかった）
dp[i][i] = 1
t(i, j, k)をi番目からj番目までの要素を並べ替える方法のうち，k番目の要素とk+1番目の要素を最後に交換する方法の数とすると，dp[i][j]は，t(i, j, k) (i <= k < j)の和になる．
t(i, j, k)は，数列をi~k, k+1~jまでの数列に分割して並べ替えた後，k番目の要素とk+1番目の要素を最後に入れ替えるというように考える．
2つの数列を並べ替える方法はそれぞれdp[i][k]，dp[k+1][j]で，その手順の数はk-i，j-(k+1)回．(ここに気がつかなかった）
この2種類の手順を組み合わせて実行する．それぞれの手順は独立に考えることができるので，
t(i, j, k) = C(j-i-1, k-i)*dp[i][k]*dp[k+1][j]（コンビネーションを使う発想がなかった．）
当然すべて適用していいというわけではなく，i~jまでの要素を確実に昇順にソートしないといけない．
上記の方法を適用して，i~jまでの数列をソートするには，
p[i], p[i+1], .. , p[k-1], p[k+1], p[k], p[k+2], p[k+3], .. , p[j]が昇順である必要がある．
つまり，p[i], p[i+1], .. , p[k-1], p[k+1]を昇順に並べ替えたときの結果と，p[i], p[i+1], .. , p[j]を昇順に並べ替えた結果のp[i] .. p[k]が等しいものだけを加算する．
この計算量は，dpを埋めるのにO(N^2)，各dp[i][j]を計算するのにO(N)かかるので，O(N^3)．
C(n, r)は，dpで事前に求めておく．
制約に合致するかどうかも事前に計算して配列に保存しておける．こちらはO(N^3logN)かかる．
Nは最大でも50なので，log 50 / log 2 = 5.6...
掲載するソースは，合致するかどうかいちいちソートして調べているので，O(N^4logN)．
あと，再帰をメモ化するタイプのDPです．漸化式をもとにループで計算している例は，TopCoderの解説にあります．
const int DIV = 1000000007; class AdjacentSwaps { public: int c[51][51]; int dp[60][60]; int init(){ memset(c, 0, sizeof(c)); for(int i=0;i<=50;++i){ for(int j=0;j<=i;++j){ if(j == 0 || j == i){ c[i][j] = 1; } else{ c[i][j] = (c[i-1][j-1] + c[i-1][j]) % DIV; } } } memset(dp, -1, sizeof(dp)); } int calc(int s, int e, vector<int> &p){ if(s == e){ return 1; } if(dp[s][e] >= 0){ return dp[s][e]; } dp[s][e] = 0; for(int k=s;k<e;++k){ bool flag = true; vector<int> v(p), w(p); sort(v.begin() + s, v.begin() + (e + 1)); sort(w.begin() + s, w.begin() + (k + 1)); for(int i=s;i<k;++i){ flag = flag && v[i] == w[i]; } flag = flag && v[k+1] == w[k]; if(!flag){ continue; } int l = calc(s, k, p); int r = calc(k+1, e, p); int t = ((long long)l * r) % DIV; t = ((long long)t * c[e-s-1][k-s]) % DIV; dp[s][e] = (t + dp[s][e]) % DIV; } return dp[s][e]; } int theCount(vector <int> p) { int res; int n = p.size(); init(); res = calc(0, n-1, p); return res; } };