裏紙

ほぼ競プロ、たまに日記

AGC 005 D - ~K Perm Counting

問題

D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder

問題概要

長さnの順列a_1 , a_2 , ... , a_nがある。i = 1,2, ... , nについて、 | a_i - i | \neq kを満たすような順列は何通りあるか、答えを924844033 (素数)で割った余りを求めよ。

イデア

答えを直接求めに行くのではなく、余事象を求めることにする。つまり、「あるiについて、 |a_i - i | = kを満たすような順列」を数え上げる。この絶対値の式で記述された条件を分離させて、a_i = i-k , a_i = i+k2n個の条件に分離させておく。

ここで、解説でも触れられている通り、長さnの順列と左側と右側にそれぞれ頂点がn個ずつ(L_1 , ... , L_n , R_1 , ... , R_nと表すことにする)存在する二部完全グラフのマッチングは一対一に対応する(全単射が存在する)(a_i = jと辺(L_i , R_j )を対応付けることで実現可能である)ので、求めたいものは「辺(L_i, R_{i-k} ) , (L_i, R_{i+k} )のうち少なくとも1つはその辺を使う完全マッチングの個数」と言い換えられる。

ということで、この2n本の辺のなかからいくつかを選び、それらを全て辺として含むような完全マッチングを考えてみることにする。辺をa本選ぶとする時、条件を満たすようなマッチングの個数は0個または(n-a)!個のどちらかになる。まず、0個になるようなものは選んだ辺がマッチングでない時で、選ばれたa本の辺がマッチングになっている時は左側と右側からそれぞれa個の頂点が選ばれて辺が結ばれてそれぞれ辺と結ばれていない頂点がn-a個ずつ残っているので、それらを結ぶ方法は(n-a)!通りであることになる。

後分かればいいことは、「2n本の中からa本選ぶときにそれがマッチングであるものは何通りか」が分かれば(これがM_a通りであるとき)、辺をa個選ぶときのマッチングの個数は M_a * (n-a)!個ということになる。そして、包除原理によって、求めたいものの個数は \displaystyle \sum_{i=1}^{n} (-1)^{i+1} * M_i * (n-i)!であるとわかる。

それでは最後に具体的にM_aを求めることを考えていく。二部グラフの形を考えてみると、グラフがいくつかの直線的なグラフで構成されていることが分かる。具体的にn=4,k=1の場合を考えてみると、まず以下のような二部グラフが構成できる。

f:id:imulan:20161005193338p:plain

そして、これを見えやすい形に直すと次のようになっている。

f:id:imulan:20161005193434p:plain

さて、このようにいくつかの連結成分に分かれているそれぞれが直線型のグラフなので、E本の辺の中からa本の辺を使うマッチングがいくつあるかを計算するには、DPで実現できる。DPで更新していくときに、dp[idx][num][prev]=今edge番まで辺を使うか否かを決めていて使うことにしている辺の個数はnum個、直前の辺を使っているか(prev)という状況のときの組み合わせの個数を保存しながら計算していけば良い。そして、このDPを更新していくときに図で言うところの左上から順に辺に番号をつけて、i番とi+1番の辺がつながっているかどうかをDPをする前に辺を構成しながら保存しておく(私の実装上ではconnected_prevとして保存)とDPの更新がシンプルに実現できる。

そして、M_a = dp[E ][a ][0 ] + dp[E ][a ][1 ]となる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

const ll mod=924844033;

ll dp[4002][2002][2]={0};
ll fact[2001];

int main()
{
    fact[0]=1;
    for(ll i=1; i<=2000; ++i) fact[i]=(i*fact[i-1])%mod;

    int n,k;
    cin >>n >>k;

    vector<bool> vis(2*n,false);
    vector<pi> edge;
    vector<bool> connected_prev;
    rep(i,n)
    {
        if(vis[i]) continue;

        int ii=i;
        int jj=i-k;
        if(jj<0) jj+=2*k;

        if(jj>=n) continue;

        edge.pb(pi(ii,jj));
        connected_prev.pb(false);
        while(1)
        {
            if(ii<jj) ii+=2*k;
            else jj+=2*k;

            if(ii>=n || jj>=n) break;

            edge.pb(pi(ii,jj));
            connected_prev.pb(true);
            vis[ii]=vis[jj+n]=true;
        }
    }

    int E=edge.size();

    dp[0][0][0]=1;
    rep(i,E)
    {
        rep(j,min(2001,i+1))
        {
            // i番目の辺を使う
            (dp[i+1][j+1][1] += dp[i][j][0]) %= mod;
            if(!connected_prev[i]) (dp[i+1][j+1][1] += dp[i][j][1]) %= mod;

            // i番目の辺を使わない
            (dp[i+1][j][0] += dp[i][j][0]+dp[i][j][1]) %= mod;
        }
    }

    vector<ll> M(E+1);
    rep(i,E+1) M[i] = (dp[E][i][0]+dp[E][i][1])%mod;

    ll sub=0;
    for(int i=1; i<=min(E,n); ++i)
    {
        if(i%2==0) sub = (sub - (M[i]*fact[n-i])%mod + mod)%mod;
        else sub = (sub + (M[i]*fact[n-i])%mod)%mod;
    }

    ll ans=(fact[n]-sub+mod)%mod;
    cout << ans << endl;
    return 0;
}