■A - コンテスト(Typical DP Contest)
https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
Π(1+x^p)
■D - Polynomial division (ABC245)
https://atcoder.jp/contests/abc245/tasks/abc245_d
b=c/a
ただしライブラリによってはa[0]!=0じゃないとREするので注意
■D - Redistribution(ABC178)
https://atcoder.jp/contests/abc178/tasks/abc178_d
Σ[x^(s-3*i)]Binom( (s-3*i)+(i-1),(i-1))
■D - Leaping Tak(ABC179)
https://atcoder.jp/contests/abc179/tasks/abc179_d
f = Σ(x^l[i]-x^(r[i]+1)))/(1-x)として
求めるのは
Σ[x^(n-1)]f^nなので
Σ[x^(n-1)]1/(1-f)
■D - Digits Parade
https://atcoder.jp/contests/abc135/tasks/abc135_d
これは普通にdpします
■F - Knapsack for All Subsets(ABC169)
https://atcoder.jp/contests/abc169/tasks/abc169_f
fi=1+x^aiとして
[x^s](Π(1+fi))-1について考えればいい
■B - RGB Coloring(AGC025)
https://atcoder.jp/contests/agc025/tasks/agc025_b
[z^K](z^0 + z^A + z^B + z^(A+B))^n
= [z^K](1 + z^B)^n * (1 +z^A) ^n
■F - Many Many Paths(ABC154)
https://atcoder.jp/contests/abc154/tasks/abc154_f
これはFPSするまでもなく、パスカルの三角形上の長方形和が分かればいい
これはホッケースティックをすればいい
■F - Strivore(ABC171F)
https://atcoder.jp/contests/abc171/tasks/abc171_f
考察をすると
f25=1/(1-25x)
f26=1/(1-26x)として
[x^k]f25^s.size()*f26が答え
前半パートはBinomの形になるので求まる
■F - Knapsack for All Segments(ABC159F)
https://atcoder.jp/contests/abc159/tasks/abc159_f
ABC169Fと同じように考えて
fi = 1+x^aiとして良さそう
求めるのは小さい方から考えて
f0
f0 + f1 + f0f1
f0 + f1 + f0f1 + f1f2 + f0f1f2 + f2
となるこれは差分を取って睨みつけると
F[0]=f0
F[1]=f1+f0f1
F[2]=f1f2+f0f1f2+f2となり
F[i]=F[i-1]*f[i]+1となるので求まる
