AGC019 E : Shuffle and Swap(1700)
作成日：2017.09.16
最終更新日：2017.09.16
問題概要
$0$と$1$からなる同じ長さの文字列$A,B$があり、それぞれ$k$個の$1$が含まれている。
数列$\{a_i\},\{b_i\}$をそれぞれ$A,B$で$1$が出現する位置の添え字を無作為に並び替えたものとする。
$1$から$k$について順に$A_{a_i}$と$A_{b_i}$の値を入れ替えた時、$A,B$が一致する確率を$P$とする。
この時$Z = P \times (k!)^2$は整数である。$Z$を$998244353$で割った余りを求めよ。
制約
$1 \leq |A| = |B| \leq 10^4$
考え方
$(A_i,B_i)$の取る値は4通りであるが、このうち$(0,0)$は解に影響しないので無視する。
また問題の条件から$(1,0),(0,1)$となるものは同数存在することが分かる。
さらに添え字によって定められた順序は解に関係ないことから、文字列$A,B$は$(A_i,B_i)=(1,1)$となる個数$x$と$(A_i,B_i)=(1,0)$となる個数$y$の2つの数で特徴づけられる。
すなわち解は$f(x,y)$という関数で表される。
また$Z$は確率を事象の数でかけたものであるから、求めるべきものは条件を満たす数列の並べ方の数である。
$f$の漸化式を立てることを考える。
$y=0$の時は必ず$A=B$であり、値を入れ替える操作を行っても数列は変化しないので、$f(x,0) = (x!)^2$である。
$y \neq 0$の時、$(A_i,B_i)$で$(1,0)$及び$(0,1)$となるものが存在するが、これらは1回しか値が変化しない。
よって$(1,0)$は$(0,1)$と入れ替わる必要があり、$(0,1)$は$(1,1)$または$(1,0)$と入れ替わる必要がある。
$(0,1)$と$(1,1)$が入れ替わった時、入れ替わらない$(1,1)$とまだ1回入れ替わる$(0,1)$が生成される。
つまり$(0,1) \leftrightarrow (1,1) \leftrightarrow ... \leftrightarrow (1,1) \leftrightarrow (1,0)$の順で入れ替われば良い。
このような列で$(0,1)$を固定した時の選び方は$(1,1)$の個数を$n$とすると$y{}_x P _n$である。
数列$\{a_i\}$上では$n+1$個の位置を占めることから、$f(x,y) = \sum_{n=0}^x{y{}_x P _n {}_{x+y} C _{n+1} f(x-n,y-1)}$であることが分かる。
この漸化式を愚直に計算すると計算量は$O(x^2 y) = O(|A|^3)$となり間に合わないので工夫する。
そのために漸化式を簡単にすることを考える。
$y \neq 0$の時の漸化式は$f(x,y) = \sum_{n=0}^x {\frac{y x! (x+y)!}{(x-n)! (n+1)! (x+y-n-1)!} f(x-n,y-1)}$であるが、
分母の$(x-n)!$及び$(x+y-n-1)!$は左辺の$f$を展開して分子に現れるため、$x!(x+y)!$を残して打ち消される。
また$y$を含む因子だけを見ていくと最終的に$y!$が現れることが分かる。
よって$f(x,y) = x! y! (x+y)! g(x,y)$とおくと、$g(x,0) = 1 , g(x,y) = \sum{\frac{g(x-n,y-1)}{(n+1)!}} (y > 0)$であることが分かる。
$g$の漸化式に含まれる係数は$x$にも$y$にも依存せず、$x$の差分のみに依存する。
したがって、高速フーリエ変換を用いた畳み込み演算を用いることができ、$O(xy \; log \: x)$に計算量を落とすことができる。
具体的にはすべて$1$からなる数列に第$i$項が$\frac{1}{(i+1)!}$の数列を$y$回畳み込めば良い。
これは繰り返し二乗法を用いることできるから、計算量は$O(x \; log \: x \; log \: y) = O(|A| (log \; |A|)^2)$となり十分高速である。
ソースコード
マクロ等はこちら
void conv(vector &a , vector &b , LL mod)
$mod$を法とする整数環高速フーリエ変換を用いて$a$と$b$で畳み込み演算を行い、結果は$a$に返す
const LL mod = 998244353;
const int MC = 10010;
LL fct[MC]; //n!
LL inv[MC]; //(n!)^(-1)
char A[MC] , B[MC];
vector<LL> ans;
vector<LL> base;
void build(){
fct[0] = fct[1] = 1;
repp(i,2,MC+1){
fct[i] = fct[i-1] * i % mod;
}
LL x = fct[MC];
inv[MC] = 1;
for(int i = mod - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (inv[MC] *= x) %= mod;
(x *= x) %= mod;
}
repm(i,MC,0){
inv[i-1] = inv[i] * i % mod;
}
}
int main(){
build();
scanf("%s %s" , A , B);
int x = 0 , y = 0;
for(int i = 0 ; A[i] ; ++i){
if(A[i] == '0') continue;
if(A[i] == B[i]) ++x;
else ++y;
}
repp(i,0,x+1){
ans.PB(1);
base.PB(inv[i+1]);
}
for(int i = y ; i > 0 ; i >>= 1){
if(i%2){
conv(ans,base,mod);
ans.resize(x+1);
}
conv(base,base,mod);
base.resize(x+1);
}
printf("%lld\n" , ans[x] * fct[x] % mod * fct[y] % mod * fct[x+y] % mod);
return 0;
}解法まとめ
すべて$1$からなる数列に第$i$項が$\frac{1}{(i+1)!}$の数列を$y$回畳み込んだ数列を高速フーリエ変換と繰り返し二乗法で求める。(34-45行)
その数列の第$x$項に$x! y! (x+y)!$をかけたものが解。(46行)