■M - Candies(EDPCM)
https://atcoder.jp/contests/dp/tasks/dp_m
[x^k]Π(1-x^(a+1))/(1-x)
■D - Binomial Coefficient is Fun(ARC110D)
https://atcoder.jp/contests/arc110/tasks/arc110_d
f_i=ΣBinom(b,a_i)x^bとして
求めるものは
[x^m]1/(1-x)*Πf_iであり
f_iを睨みつけると負の二項係数を思い出すので
f_i=x^a_i/(1-x)^(a_i+1)がわかり
[x^m]1/(1-x)*Πf_i
=[x^(m-Σa)]1/(1-x)^(Σai+n+1)で
もう一度、負の二項係数を思い出すと
Binom(m+n,Σa+n)
■E - キャンディーとN人の子供(ARC059C)
https://atcoder.jp/contests/arc059/tasks/arc059_c?lang=ja
gi = Σ(x_i*z)^a = 1/(1-x_i*z)
f(x_1,x_2,x_3.....) = [x^c]Πgi
なので答えは
[x^c]ΣΠgi = [x^c]ΠΣgi
■D - 漸化式 (ABC009D)
https://atcoder.jp/contests/abc009/tasks/abc009_4
これは普通に行列累乗。
FPSでやるのはよくわからん
■D - Multiset Mean (ARC104)
https://atcoder.jp/contests/arc104/tasks/arc104_d
[x^0]Π(1-x^( ( j-i )*(k+1)))/(1-x^ ( j-i ) )で求まるのはすぐわかる。
xの肩に乗る数が負になるのは適当に下駄を履かせてごまかすといい。
しかし、これでもまだTLEするので、睨みつけるとずらしながら答えが出せる
■F - 準急(TDPC)
https://atcoder.jp/contests/tdpc/tasks/tdpc_semiexp
最後にバツを書く場所を考えると
k=2だと
x,oxの繰り返しで埋めていく感じ
なのでf(x)=x( ( 1-x^(k+1))/(1-x))
とおくと
答えは(f(x)-1)/(1-f(x))の後ろの方の係数和
■G - Colorful Candies 2 (ABC215G)
https://atcoder.jp/contests/abc215/tasks/abc215_g
ans_k=(ΣBinom(n,k)-Binom(n-ni,k))/Binom(n,k)
なのは簡単で
fk=Σf(n-ni,k)が高速に求まればいい
f=Σfix^iについて考えると
これはΣ(1+x)^(n-ni)となるので
g(x)=Σx^(n-ni)をシフトしたもの。これはFPSライブラリにある
■G - Count Sequences(ABC276)
https://atcoder.jp/contests/abc276/tasks/abc276_g
[x^m]1/(1-x)^2*( (x+x^2)/(1-x^3))^(n-1)
がほしい。これは畳み込むとライブラリの成約を満たさないので
直接求める
■G - Farthest City
https://atcoder.jp/contests/abc281/editorial/5381
todo
普通のdp解放しか見えない
■D - Dichotomy(Xmas Contest 2022)
https://atcoder.jp/contests/xmascon22/tasks/xmascon22_d
ラグランジュ反転
これは難しいから、カタラン数の母関数とラグランジュ反転はセットで覚えておいた方がいいかも
