SRM 517 div1 med:AdjacentSwaps

問題

TopCoder Statistics - Problem Statement

解法

注目すべき特徴として,
「ある場所でスワップしたら,もうそこを挟んで数が移動することができなくなる」
ということがあります。例えば,

0 1 2 3 4

という順列で1と2をswapすると,

0 2 1 3 4

となりますが,この問題ではこのあと2と1の間のポジションの数字をswapすることが出来ないので,例えば0がこの後1の右側に来ることはありえないし,4が2の左側に来ることもありえません。

このような特徴から,区間を考えるのが上手く状態をまとめて考えると良さそうです。要するに区間DPを使うということですね。

dp[l][r] = (区間[l, r]においてp[l]からp[r]がきちんとソートされた状態になる場合の数)とします。

l <= k <= rを満たすkそれぞれについて,p[k]とp[k+1]を最後にスワップするようなもののなかで条件を満たすものを合計したものがdp[l][r]の答えになります。

ということで区間[l, r]について,最後にp[k]とp[k+1]を交換してソートした状態にするような場合の数を考えます。
この最後の交換の前にどのような状態になっていれば良いかというと,

p[l], p[i+1], .. , p[k-1], p[k+1], p[k], p[k+2], p[k+3], .. , p[r]が昇順

である必要があります。p[l], ... , p[k-1], p[k+1]およびp[k], p[k+2], ..., p[r]を昇順にするのはdp[l][k]とdp[k+1][r]の計算に任せるとして,[l, r]を調べる時点で左側にp[l], ... , p[k-1], p[k+1]があって右側にp[k], p[k+2], ..., p[r]がある状態でないと話になりません(最初に話した「越境」的なことができないということから)。

この条件を満たしているのか調べて,OKならさらに「k番目でスワップするような場合の数は何通りあるのか」という計算に進みます。

上で話したことにより,kより左側とkより右側は独立に動かすことが出来ます。この左側と右側動かす順番は適当で良いので通りあります。よって,この場合の数は

通り

となります。これを頑張って計算すれば答えを求めることが出来ます。

const int MAXN = 55;
const ll MOD = 1e9+7;
ll dp[MAXN][MAXN];
ll nCr[MAXN][MAXN];

void print(vector<int> p) {
    for (int el : p) cout << el << "  ";
    cout << endl;
}

vector<int> p;

ll dfs(int l, int r) {
    if (r == l) return 1;
    ll& ret = dp[l][r];
    if (ret >= 0) return ret;
    ret = 0;
    for (int i = l; i < r; i++) {
        bool flag = true;
        vector<int> v(p), w(p);
        sort(v.begin()+l, v.begin()+(r+1));
        sort(w.begin()+l, w.begin()+(i+1));
        for (int j = l; j < i; j++) {
            flag &= (v[j] == w[j]);
        }
        flag &= (v[i+1] == w[i]);
        if (!flag) continue;
        ll temp = (dfs(l, i) * dfs(i+1, r)) % MOD;
        (temp *= nCr[r-l-1][i-l]) %= MOD;
        (ret += temp) %= MOD;
    }
    return ret;
}

class AdjacentSwaps {
public:
    int theCount(vector <int> p) {
        ::p = p;
        for (int i = 0; i < MAXN; i++) {
            nCr[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                nCr[i][j] = (nCr[i-1][j] + nCr[i-1][j-1]) % MOD;
            }
        }
        int n = p.size();
        memset(dp, -1, sizeof(dp));
        return dfs(0, n-1);
    }
};