積の和典型
自分用の書き換え
■例題
長さがn総和がmな整数列Aの全て対して
ΣΠA[i]を求めよ
o:=m-n個
x:=n個
! :=n-1個の並び替えを考える。但しxと!は交互に配置する
つまりBinom(m+n-1,2*n-1)で求まる
■D - Binomial Coefficient is Fun（AtCoder Regular Contest 110）
基本的には上の例題と同じ
以下の処理を一旦個別に考えてみる
和が4
x|xx|xなので1
和が5
x|xx|xにoを挿入するのでBinom(7,1)
まとめて考える
仕切りを一つ増やす
x|xx|x|にoを挿入する
一番右の仕切りの右に入ったものは無視すると以下を表現できる。
よって
Ans = Binom(n + m,m-suma) = Binom(n+m,n+suma)
■C - Cookie Distribution(第6回 ドワンゴからの挑戦状 予選)
入力例１で考える
12=(1+0)*(1+1)*(1+1)+(1+1)*(1+0)*(1+1)+(1+1)*(1+1)*(1+0)
これは一般化すると
xij:=人iがj日目に貰う1貰わないなら0とし
Ans = Σ(x11+x12)*(x21+x22)*(x31+x32)
展開すると
Ans=Σ(x11x21x31+x11*x21*x32+.......)
Ans=Σx11x21x31+Σx11x21x32+.......
dpを考える。だが、見る向きを変えて、日でみたい。
dp[i][j]:=i日目まで考えた、j人分は既に割当済みとする
すると配るdpで考えて
dp[i+1][j+k]+=dp[i][j] * Binom(n-j,k) * Binom(n-k,a-k)
で遷移できる
Binom(n-j,k):=未割り当てのn-j人から今回割り当てるk人を選択する
Binom(n-k,a-k):=今回割り当てられたk人以外のn-k人に残りのa-k個の割当
に相当する
■G - Balls in Boxes(AtCoder Beginner Contest 231)
fpsのほうが自然だけど
まずAが全て0の時の場合を考えてみる。
サンプル0
2 3
0 0
を用意して考えてみる。
答えは12/2^3なのは明らか。
操作列に操作する対象の数字をふるとして
代表なもの(今まででいうx)は別扱いすると
1!,2!,1*∞,2*∞から1!と2!は絶対選択して、あとは1,2を好きなだけ選べばいい。
つまり3*2*2^1になる。
次にAが0じゃないときのことを考える。
この場合代表的なものがAに含まれる可能性もあるので
代表が何個Aから選ぶかで分けると
前計算としてdp[i]:=Aからi個選択したもの積の和をO(n^2)で求めておくと
for(int i = 0;i < n;++i){// Aから代表が選ばれる物の数
mint sub = dp[i];
sub += k *(k-1) * (k-2)*.......(k-n+i+1);
sub *= pow_mod(n,k-n+i,mod);
ans +=sub;
}
ans /= pow_mod(n,k,mod);
で求まる。
■D - Sets Scores(AtCoder Regular Contest 147)
SiとSi+1の差分の要素をXiとする
Xを固定する(Xの種類数は当然 m^(n-1))
S1とX固定するとSはすべて決まる
S1にaが含まれているときにSにaが含まれている個数をzaとすると
S1にaが含まれていないときにSにaが含まれている個数はn-zaとなる
なので
(za+n-za)*(zb-m-zb)*.....
となりn^m
よって答えはn^m*m^(n-1)
■H - Social Distance 2(AtCoder Beginner Contest 225)
k=0のときのことを考える。
椅子が5つあって2人座るとすると
o:=座られる椅子
x:=空き椅子
!:=区切り
xxox!oのようなことを考えるので
Binom(n+(k-1),(k-1)+k)で求まる
同じように考えると
◆椅子がn個あって両端に人がすでに座っている、追加でk人座る
Binom( ( n-2)+(k+1),k+(k+1))
◆椅子がn個あって片側に人がすでに座っている、追加でk人座る
Binom((n-1)+k,k+k)
これをそれぞれの区間についてfpsの形にして求め
convolutionしたものの m-k次が答えになる。
以下も同じ要領で解けるらしいがいまいち解けず。
■E - BBQ Hard(AtCoder Grand Contest 001)
■E - Pass to Next(AtCoder Regular Contest 124)
追加(2022/11/19)
OMC126-D
a+b+c=n
ΣΠ(abc)^2
p=ΣΠ(abc)^2
q=ΣΠ(ab)^2*c
r=ΣΠa^2*bc
s=ΣΠabc
とおく
binom(n+2,8)=ΣΠbinom(a,2)*binom(b,2)*binom(c,2)
binom(n+2,7)=ΣΠbinom(a,2)*binom(b,2)*binom(c,1)
binom(n+2,6)=ΣΠbinom(a,2)*binom(b,1)*binom(c,1)
binom(n+2,5)=ΣΠbinom(a,1)*binom(b,1)*binom(c,1)
展開し対称性を考慮すると
binom(n+2,8)=p-3q+3r-s
binom(n+2,7)=q-2r+s
binom(n+2,6)=r-s
binom(n+2,5)=s
となる
あとはsから順々に求めるとpが求まる
