SRM517 Div1 Medium(600) AdjacentSwaps

AdjacentSwaps

それぞれのカードの移動前の後の位置から、ウサギが呼ばれる順番の満たす制約が得られる。例えば4番目の例の

1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15, 19, 17

だと、3が3番目から1番目に移動していることで、数字をウサギの番号として、2→1と0→1と2→3という制約が、6が6番目から9番目に移動していることで、6→7→8と6→5と9→8という制約がかかる。移動の間のウサギは移動方向と同じ順番に呼ばれ、両端のウサギは逆順に呼ばれる。3→4と4→3というような矛盾する制約があったら答えは0。例の制約を図にすると以下のようになる。

 1,  3,  0,  5,  2,  7,  4,  8, 10,  6, 12,  9, 14, 11, 16, 13, 18, 15, 19, 17
   0→ 1← 2→ 3← 4→ 5← 6→ 7→ 8← 9→10←11→12←13→14←15→16←17→18

この制約を満たすウサギの並び順の総数が答え。動的計画法で求める。i番目までのウサギを並べた時にi番目のウサギがj番目に呼ばれる場合の数を覚えておく。

#include <vector>
#include <numeric>
using namespace std;

class AdjacentSwaps{public:
int theCount( vector <int> p )
{
    int M = 1000000007;
    int n = (int)p.size();

    vector<int> D(n);

    for ( int i=0; i<n; i++ )
    {
        if ( i==p[i] )
            return 0;
        int d = p[i]<i ? 1 : -1;

        vector<int> t(n);
        t[p[i]] = -d;
        for ( int j=p[i]+d; j!=i; j+=d )
            t[j] = d;
        t[i] = -d;

        for ( int j=1; j<n-1; j++ )
        if ( t[j]!=0 )
        {
            if ( D[j]!=0 && D[j]!=t[j] )
                return 0;
            D[j] = t[j];
        }
    }

    //  T[i][j]: q[0], q[1], ……, q[i]を並べてq[i]がj番目にある場合の数
    vector<vector<long long> > T( n-1, vector<long long>( n-1 ) );
    T[0][0] = 1;
    for ( int i=1; i<n-1; i++ )
    for ( int j=0; j<=i; j++ )
    {
        if ( D[i] > 0 )
            for ( int k=0; k<j; k++ )
                T[i][j] += T[i-1][k];
        else
            for ( int k=j; k<i; k++ )
                T[i][j] += T[i-1][k];
        T[i][j] %= M;
    }
    
    return (int)(accumulate(T[n-2].begin(),T[n-2].end(),0ll)%M);
}};