この記事は帰ってきた AOJ-ICPC Advent Calendar 2022の7日目の記事です。
問題概要
整数 $N$ が与えられます。 ここで長さ $N$ の順列 $p$ のスコア $f(p)$ を以下のように定義します。
- $N$ 頂点で、 $i\rightarrow p_{i}$ に辺が貼ってあるグラフの連結成分の大きさの総積
$p$ は $N!$ 通りありますが、このとき、 $f(p)$ の分散を $\text{mod} (10^{9}+7)$ で求めてください。
$1\leq N\leq 10^{5}$
分散の公式
$V[f(p)]=E[(f(p))^{2}]-(E[f(p)])^{2}$
つまり、スコアの平均と、スコアの二乗の平均が求まれられればいいです。
例
$N=3$ のとき、
$p=(1,2,3)$ なら $f(p)=1$
$p=(1,3,2)$ なら $f(p)=2$
$p=(2,1,3)$ なら $f(p)=2$
$p=(2,3,1)$ なら $f(p)=3$
$p=(3,1,2)$ なら $f(p)=3$
$p=(3,2,1)$ なら $f(p)=2$
よって、$E[(f(p))^{2}]=\frac{31}{6},(E[f(p)])^{2}=\frac{169}{36}$ より、 $V[f(p)]=\frac{17}{36}$ です。
解法
まず、前提として 二項係数や階乗、階乗の逆数は事前計算 $O(N)$ で $O(1)$ で求まります。
総積の平均、つまり総積の和が求めることができればいいので、いわゆる積の和典型というものを使うことで解くことができます。
積の和典型については他の人の記事に任せます。
スコアの平均
スコアの和が求まればいいです。
積の和典型を用いて一つの連結成分の中から一つ要素を選ぶことを考えます。
要素が $1$ 以上 $N$ 以下の整数の集合 $S$ のうち、空集合でないのは $2^{N}-1$ 個ありますが、これら全てについて、以下の問題の答えを求め、その和がスコアの和と等しくなります。
- 連結成分の数が $|S|$ と等しくて、 $S$ に含まれているどの異なる二つの要素も同じ連結成分に含まれないような $p$ の数を求めなさい。
$N=6,S=(3,4,5)$ のとき、以下のようなグラフがあり得ます。
$N,S$ が決まっているとき、このグラフが何通りあるかを求めばいいです。
このグラフの数が、以下の条件を全て満たす順列 $q$ の数と同じです。
- $q$ の最初の要素は $S$ の要素のうち最小のものと同じ。
- $S$ に含まれている異なる二つの要素 $a,b$ について、 $a<b$ なら $a$ の方が $b$ より早く $q$ に出てくる。
グラフと上記の条件を満たす $q$ は一対一対応しています。例えば、上の図のグラフは $q=(3,2,4,5,6,1)$ と対応しています。
この変換はグラフが $3\rightarrow 2,4,5,\rightarrow 6\rightarrow 1$ の形であるからです。
よって、 $N,S$ が決められたとき、 $q$ の場合の数は $(N-|S|)!\binom{N-1}{|S|-1}$ で、 $N,|S|$ が決められたとき、 $S$ の場合の数は $\binom{N}{|S|}$ なので、スコアの和は $|S|$ を決めると $O(1)$ でもとまるので、合計 $O(N)$ で求まります。
スコアの二乗の平均
スコアの二乗の和が求まればいいです。
一つの連結成分から順番を決めて二つ取ることを考えます。
二つとったときに、同じ要素である連結成分が $a$ 個、違う要素である連結成分が $b$ 個のとき、とった要素の場合の数とグラフの場合の数の積について考えます。
まず、要素の場合の数は、 $\binom{N}{a}\binom{N-a}{b}\frac{(N-(a+b))!}{(N-(a+2b))!}$ です。
グラフの数は前のスコアの平均の際、グラフの数を求める際に $q$ との一対一対応を考えたときと同じように考えると $\binom{N-1}{a+2b-1}$ となります。
これらの積は以下のようになります。
$$\frac{(N-1)!N!}{a!b!(a+2b-1)!(N-(a+2b))!}$$
よって、$1\leq a+2b\leq N$ かつ $0\leq a,b$ を満たす全ての $a,b$ に対して、上記の式の和を求めればいいです。
愚直にやると $O(N^{2})$ なので、これを高速化する必要があります。
例えば $c=a+2b$ を固定して考えることで、多項式 $f(x)=\sum \frac{x^{i}}{i!},g(x)=\sum \frac{x^{2i}}{i!}$ の積を求め、$x^{c}$ の係数に $\frac{1}{(c-1)!(N-c)!}$ をかけたものの総和を計算するという求め方で、任意 mod 畳み込みを用いて $O(N\log N)$ で求まりますが、実は畳み込みを用いないで求めることができます。
まず、$h(x)=(1+x)^{N-1}$ とすると $\frac{(N-1)!}{(c-1)!(N-c)!}=\binom{N-1}{N-c}$ であることから、スコアの二乗の和は $f(x)g(x)h(x)$ の $x^{N}$ の係数に $N!$ をかけたものに等しいです。 $f(x)=e^{x},g(x)=e^{x^{2}}$ なので、以下が成り立ちます。
$f(x)g(x)h(x)=e^{x+x^{2}}(1+x)^{N-1}=\sum\frac{1}{i!}x^{i}(1+x)^{N-1+i}$
$i=1,2,...,N$ に対して、 $x^{N}$ の係数を求めるのは $O(1)$ でできるため、合計 $O(N)$ でスコアの二乗の和を求めることができました。
コード
modint ではないので、計算のたびに mod で割らないといけないのですが、見やすさのため main 関数内では省いています。
#include <bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,a,b) for (ll i=a;i<b;i++) namespace po167{ struct combination{ int upper; long long MOD; std::vector<long long> fact; std::vector<long long> rev; std::vector<long long> fact_rev; combination(int max,long long _mod):upper(max),MOD(_mod),fact(max+1),rev(max+1),fact_rev(max+1){ for(long long i=0;i<=max;i++){ if(i<2){ fact[i]=1; fact_rev[i]=1; rev[i]=1; continue; } fact[i]=(fact[i-1]*i)%_mod; rev[i]=_mod-((_mod/i)*rev[_mod%i])%_mod; fact_rev[i]=(fact_rev[i-1]*rev[i])%_mod; } } void upper_change(int n_upper){ assert(n_upper<MOD); while(upper<n_upper){ upper++; fact.push_back(fact[upper-1]*upper%MOD); rev.push_back(MOD-((MOD/upper)*rev[MOD%upper])%MOD); fact_rev.push_back((fact_rev[upper-1]*rev[upper])%MOD); } } long long Comb(int x,int y){ upper_change(x); if (x<y||y<0||x<0) return 0; return (((fact_rev[y]*fact_rev[x-y])%MOD)*fact[x])%MOD; } long long P(int x,int y){ upper_change(x); if (x<y||y<0||x<0) return 0; return (fact_rev[x-y]*fact[x])%MOD; } }; } using po167::combination; int main() { const ll mod=1e9+7; int N; cin>>N; ll ans=0; combination table(N*2,mod); ll tmp=0; rep(i,1,N+1){ tmp+=(table.fact[N-i]*table.Comb(N,i)*table.Comb(N-1,i-1)); } tmp*=table.fact_rev[N]; ans=-(tmp*tmp); rep(i,1,N+1){ tmp=table.fact_rev[i]*table.Comb(N-1+i,N-i); ans+=tmp; } cout<<ans<<"\n"; }
