kmjp's blog

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

Codeforces #537 Div2 D. Destroy the Colony

Codeforces

久々の戻すDP。
http://codeforces.com/contest/1111/problem/D

問題

偶数長(N文字)の文字列Sが与えられる。
Sの要素を並べ替え、同じ種類の文字が前半分か後ろ半分にすべて集まっている状態を正しい状態とする。

以下のクエリQ個に答えよ。

  • S中の2要素S[x],S[y]が指定される、Sを並べ替えてできる文字列のうち、S[x]とS[y]が同じ側(前半分ないし後ろ半分)に固まり、かつ正しい状態は何通りか。

解法

文字の種類は52種類なので、S[x],S[y]の組み合わせはQに比べさほど多くない。
なので事前に列挙してしまおう。

この問題は、本質的には各文字種を前半分に入れるか後ろ半分に入れるかを求めるナップサック問題である。
前半分および後ろ半分内での並び順を無視し、以下を考えよう。
f(a, p, q) :=文字p,q以外の文字種のうち、前半分に入るものが計a文字分であるような分類のしかた

そうすると解はf(N/2, S[x], S[y]) * 2 * (N/2)! * (N/2)! / (C['a']!*C['b']!....)となる。
2を掛けるのは、S[x],S[y]が前に来る場合と後ろに来る場合をそれぞれ考えるためである。
(C[c]はSにおけるcの文字数とする。)

あとはf(a,p,q)を求めれば良いことになる。
ここで戻すDPを使おう。まず、全文字を使う以下のケースを考えよう。
これは単なるナップサック系の数え上げなのでO(Nw) (wは文字種別の数)で片が付く。
g(a) := 全文字種のうち、前半分に入るものが計a文字分であるような分類のしかた
ここから、p,qを総当たりしながら、f(N/2, p,q)を求める。

ここで戻すDPを行うのたが、戻すDPは状態遷移がわかりにくい。
そこでこの種の数え上げが、多項式の形で書けることを考えよう。
多項式P(x) = prod(1+x^C[c]) を考えると、g(a)はP(x)のa次の項となる。
そう考えると、f(a,p,q)はP(x) / (1+x^C[p]) / (1+x^C[q])となる。
この割り算はO(N)で行えるので、文字種２種を総当たりしてもf(N/2,p,q)はO(Nw^2)で列挙できる。

ll mo=1000000007;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

int N;
string S;
int C[256],Q;

ll dp[101010],dp2[101010],dp3[101010];
ll ret[52][52];


void solve() {
	int i,j,k,l,r,x,y; string s;

	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>S;
	N=S.size();
	FORR(c,S) {
		if(c>='a' && c<='z') c=c-'a';
		if(c>='A' && c<='Z') c=c-'A'+26;
		C[c]++;
	}
	
	ll pat=2*fact[N/2]*fact[N/2]%mo;
	FOR(i,52) pat=pat*factr[C[i]]%mo;
	
	dp[0]=1;
	FOR(i,52) if(C[i]) for(j=N;j>=0;j--) if(dp[j]) (dp[j+C[i]]+=dp[j])%=mo;
	FOR(x,52) {
		memmove(dp2,dp,sizeof(dp));
		for(i=N;i>=C[x];i--) {
			dp2[i-C[x]]-=dp2[i];
			if(dp2[i-C[x]]<0) dp2[i-C[x]]+=mo;
		}
		ret[x][x]=dp2[N/2];
		for(y=x+1;y<52;y++) {
			memmove(dp3,dp2,sizeof(dp2));
			for(i=N;i>=C[y];i--) {
				dp3[i-C[y]]-=dp3[i];
				if(dp3[i-C[y]]<0) dp3[i-C[y]]+=mo;
			}
			ret[x][y]=dp3[N/2];
		}
	}
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		int a,b;
		a=S[x-1];
		b=S[y-1];
		if(a>b) swap(a,b);
		cout<<(ret[a][b]*pat%mo)<<endl;
	}
}

まとめ

戻すDPは状態遷移が苦手だったが、多項式除算で考えると非常に見通しが良くなって良い。