yukicoder : No.171 スワップ文字列(Med)

★３の割には簡単。
http://yukicoder.me/problems/414

問題

文字列Sが与えられる。
任意の隣接する2文字を入れ替える、という処理を任意回数行える場合、元のSを除いて何通りの文字列を生成できるか。
生成できる文字列数を573で割った余りを答えよ。

解法

隣接する２文字を入れ替えることを繰り返すと、結局任意の並び順に出来る。
よってあとはSを並べ替えて何通りの文字列ができるか求めて、元のSの分1を引けばよい。

'A'～'Z'の文字がそれぞれ個ずつあるとし、その和をLとする。
このような同じものを含む順列の数はで計算できる。
多倍長整数が使える言語ならこれで十分。

ただし多倍長整数が利用できない言語ではこの解法は利用しにくい。
適宜mod 573を取るにしても、剰余を取るべき573が合成数のため逆元を用いた除算ができず、この式を計算するには中国人剰余定理など必要でだいぶ手間がかかる。

そこでこの式をと変形する。
(L文字中まず'A'の場所をN_a箇所決め、残りの(L-N_a)文字中から'B'の場所をN_b文字箇所決め…と考えると良い)
あとはパスカルの三角形を使えば除算を使うことなく計算できる。

別解で、A,B,C,...と順に挿入していくパターンを重複組み合わせを使って求める方法もある。

string S;
int L;
ll mo=573;
int num[26];

const int CN=2001;
ll C[CN][CN];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	
	cin>>S;
	L=S.size();
	FOR(i,S.size()) num[S[i]-'A']++;
	
	ll ret=1;
	FOR(i,26) if(num[i]) {
		ret = ret * C[L][num[i]] % mo;
		L-=num[i];
	}
	cout<<(ret+mo-1)%mo<<endl;
	
}

まとめ

Hard(★４)を作るとしたら、どこをいじれば面白くなるかな。