AGC 005 D - ~K Perm Counting
問題
D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder
問題概要
長さの順列がある。について、を満たすような順列は何通りあるか、答えを (素数)で割った余りを求めよ。
アイデア
答えを直接求めに行くのではなく、余事象を求めることにする。つまり、「あるについて、を満たすような順列」を数え上げる。この絶対値の式で記述された条件を分離させて、の個の条件に分離させておく。
ここで、解説でも触れられている通り、長さの順列と左側と右側にそれぞれ頂点が個ずつ(と表すことにする)存在する二部完全グラフのマッチングは一対一に対応する(全単射が存在する)(と辺を対応付けることで実現可能である)ので、求めたいものは「辺のうち少なくとも1つはその辺を使う完全マッチングの個数」と言い換えられる。
ということで、この本の辺のなかからいくつかを選び、それらを全て辺として含むような完全マッチングを考えてみることにする。辺を本選ぶとする時、条件を満たすようなマッチングの個数は個または個のどちらかになる。まず、個になるようなものは選んだ辺がマッチングでない時で、選ばれた本の辺がマッチングになっている時は左側と右側からそれぞれ個の頂点が選ばれて辺が結ばれてそれぞれ辺と結ばれていない頂点が個ずつ残っているので、それらを結ぶ方法は通りであることになる。
後分かればいいことは、「本の中から本選ぶときにそれがマッチングであるものは何通りか」が分かれば(これが通りであるとき)、辺を個選ぶときのマッチングの個数は個ということになる。そして、包除原理によって、求めたいものの個数はであるとわかる。
それでは最後に具体的にを求めることを考えていく。二部グラフの形を考えてみると、グラフがいくつかの直線的なグラフで構成されていることが分かる。具体的にの場合を考えてみると、まず以下のような二部グラフが構成できる。
そして、これを見えやすい形に直すと次のようになっている。
さて、このようにいくつかの連結成分に分かれているそれぞれが直線型のグラフなので、本の辺の中から本の辺を使うマッチングがいくつあるかを計算するには、DPで実現できる。DPで更新していくときに、dp[idx][num][prev]=今edge番まで辺を使うか否かを決めていて使うことにしている辺の個数はnum個、直前の辺を使っているか(prev)という状況のときの組み合わせの個数
を保存しながら計算していけば良い。そして、このDPを更新していくときに図で言うところの左上から順に辺に番号をつけて、番と番の辺がつながっているかどうかをDPをする前に辺を構成しながら保存しておく(私の実装上ではconnected_prev
として保存)とDPの更新がシンプルに実現できる。
そして、となる。
実装(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; }