kmjp's blog

競技プログラミング参加記です

AtCoder ABC #214 : G - Three Permutations

ARC

解法を理解した後も、割と手間取った。
https://atcoder.jp/contests/abc214/tasks/abc214_g

問題

1～NのPermutation2つP,Qが与えられる。
同じく1～NのPermutation Rのうち、R[i]=P[i]またはR[i]=Q[i]となるiが1つもないようなものは何通りか。

解法

少なくともx個R[i]=P[i]またはR[i]=Q[i]となるiが確定している組み合わせをf(x)とする。残り(N-x)個は未確定とする。
未確定の(N-x)要素の埋め方が(N-x)!通りあると考えると、包除原理の要領で解は
\displaystyle \sum_i (-1)^i f(i) (N-x)!
である。あとはf(x)を求めることを考えよう。

N頂点からなるグラフで、P[i]-Q[i]間に辺を張ったものを考える。
R[i]=P[i]またはR[i]=Q[i]となるR[i]を選択するということは、辺の両端の点のいずれかを選択するということである（2つの辺で1つの点を共に選択することはできない)。
この考えをもとに、x個選択することを考える。

このグラフの各連結成分は、単一の点で自己ループを成すであるか閉路を成すものである。
単一の点については、その点がR[i]=P[i]=Q[i]となるR[i]は1通り。
閉路の場合、閉路中の全辺を選択する場合は2通りで、そうでない場合、選択した辺からなる連結成分毎に、その頂点数分の選択肢がある。

後者はDPで求めることができる。
「選択した辺からなる連結成分毎に、その頂点数分の選択肢がある」という条件は、「連結成分内から1つ頂点を選ぶ選び方」と言い換えることができる。
あとは連環に対するDPを行うわけだが、状態として
「最後の辺の選択の有無」「最後の連結成分の頂点選択の有無」「直前の辺の選択の有無」「直前の連結成分の頂点選択の有無」の4通りについて計2^4パターンの状態をもって頂点毎にO(N^2)でDPしていくことができる。

int N;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<3030> uf;
int P[3030],Q[3030];
ll dp[3030][3030][4];

ll from[3030];
ll to[3030];
ll cand[3030];
ll fact[3030];

const ll mo=1000000007;

void hoge(int N) {
	int x,y,i,j;
	ZERO(cand);
	
	if(N==1) {
		cand[0]=1;
		cand[1]=1;
		return;
	}
	
	
	FOR(i,4) {
		FOR(x,N+1) FOR(y,N+1) FOR(j,4) dp[x][y][j]=0;
		// 0-prev edge declined
		// 2-prev edge selected
		// 0-prev vertex declined
		// 1-prev vertex selected
		dp[0][0][i]=1;
		FOR(x,N) {
			FOR(y,N) {
				// not take edge
				(dp[x+1][y][0]+=dp[x][y][1]+dp[x][y][3])%=mo;
				(dp[x+1][y][1]+=dp[x][y][1]+dp[x][y][3])%=mo;
				
				(dp[x+1][y+1][2]+=dp[x][y][0]+dp[x][y][2])%=mo;
				(dp[x+1][y+1][3]+=dp[x][y][0]+dp[x][y][1]+dp[x][y][2]+dp[x][y][3])%=mo;
			}
		}
		FOR(x,N) {
			(cand[x]+=dp[N][x][i])%=mo;
		}
	}
	cand[N]=2;
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) cin>>Q[i];
	FOR(i,N) uf(P[i]-1,Q[i]-1);
	
	from[0]=1;
	FOR(i,N) if(uf[i]==i) {
		k=uf.count(i);
		hoge(k);
		ZERO(to);
		FOR(x,N+1) FOR(y,k+1) if(x+y<=N) (to[x+y]+=from[x]*cand[y])%=mo;
		swap(from,to);
	}
	
	fact[0]=1;
	FOR(i,N) fact[i+1]=fact[i]*(i+1)%mo;
	
	ll ret=0;
	FOR(i,N+1) {
		(from[i]*=fact[N-i])%=mo;
		if(i%2==0) ret+=from[i];
		else ret+=mo-from[i];
	}
	
	cout<<ret%mo<<endl;
}

まとめ

うーん、地味に数え上げ方に苦労した。