TopCoder SRM 472 Div1 Medium TwoSidedCards

TopCoder 動的計画法 確率・場合の数

問題

n枚のカードがある。
i枚目のカードの表にはtaro[i]の数字が書かれており、裏にはhanako[i]の数字が書かれている。
これらのカードを全て一列に並べたときに現れる数字の列は何通りあるか。

制約条件

n≦50
taro[i],hanako[i]は1〜nの整数が一度ずつ現れる。

方針

頂点がn個のグラフで、以下のようなものを考える。
表がaのカードの裏に書かれている数字をbとするとき、a番の頂点からb番の頂点に辺がある。


この、グラフはいくつかのサイクルから成り立っている。
それぞれのサイクルごとに、カードの並べ方が何通りあるかは独立に数えられるので、全て独立に数えて掛け算すれば良い。


サイクルごとにカードの並べ方が何通りあるかは、サイクルの長さだけに依存することがわかる。
サイクルの「辺ひとつにどちらの向きを付けるか」に対して「カード一枚の裏表」が一対一に対応している。


同じ数字がi回出てくるような裏表の向き付けが何通りあるかを求めたい。
これは以下のような状態を取るDPにより求めることができる。
dp[i枚まで見た][いままでの同じ数字の個数][最後のカードが裏か][最初のカードが裏か]


一回も数字がだぶらないようなカードの使い方は、最初のカードを裏にする場合と、表にする場合で、数字の組が同じであるのに、2通りにえられているので1をひく。
後はこれを足し算すれば同じ数字がi回出てくるときのカードの場合の数が求まる。

ソースコード

int n,nxt[50];
bool v[50];
int rec(int c){
	v[c]=1;
	return v[nxt[c]]?1:1+rec(nxt[c]);
}
ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d=1;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	else x=1, y=0;
	return d;
}
int inv(int n){
	ll x,y;
	extgcd(n,mod,x,y);
	return (x%mod+mod)%mod;
}
int C(int n,int k){
	ll res=1;
	rep(i,k)res=res*(n-i)%mod,res=res*inv(i+1)%mod;
	return (int)res;
}
int dp[51][51][2][2],ans[51];
int calc(int m){
	memset(dp,0,sizeof(dp));
	dp[0][0][1][1]=dp[0][0][0][0]=1;
	rep(i,m-1)rep(j,i+1)rep(k,2){
		(dp[i+1][j+1][0][k]+=dp[i][j][1][k])%=mod;
		(dp[i+1][j][1][k]+=dp[i][j][0][k])%=mod;
		(dp[i+1][j][0][k]+=dp[i][j][0][k])%=mod;
		(dp[i+1][j][1][k]+=dp[i][j][1][k])%=mod;
	}
	memset(ans,0,sizeof(ans));
	rep(i,m+1){
		(ans[i]+=dp[m-1][i][1][1])%=mod;
		(ans[i]+=dp[m-1][i][0][1])%=mod;
		(ans[i]+=dp[m-1][i][0][0])%=mod;
		(ans[i+1]+=dp[m-1][i][1][0])%=mod;
	}
	ans[0]--;
	ll res=0;
	rep(i,m+1)if(ans[i]){
		ll tmp=ans[i]; int rest=m;
		rep(j,i)tmp=tmp*C(rest,2)%mod, rest-=2;
		rep(i,rest)tmp=tmp*(i+1)%mod;
		res+=tmp;
	}
	return res%mod;
}
class TwoSidedCards {
	public:
	int theCount(vector <int> taro, vector <int> hanako) 
	{
		n=taro.size();
		vector<pi> p;
		rep(i,n)p.pb(mp(taro[i],hanako[i]));
		sort(all(p));
		rep(i,n)nxt[i]=p[i].second-1;
		ll ans=1;
		memset(v,0,sizeof(v));
		int rest=n;
		rep(i,n)if(!v[i]){
			int m=rec(i);
			ans=ans*C(rest,m)%mod*calc(m)%mod;
			rest-=m;
		}
		return (int)ans;
	}
};