Codeforces 514E

問題

無限に頂点がある根付きn分木が与えられる。
ある親頂点について、子頂点はn個あるが、それぞれ左からd[i]の重みになっている。
今、「根から頂点jまでの距離=根から頂点までの最短ルートの重みの和」とする。
距離xが与えられるので、距離がx以下であるような頂点数がいくつかをmod 1000000007で求める。

n<=10^5
x<=10^9
1<=d[i]<=100
(d[i]はdistinctとは限らない)

考え方

xが大きくて死ぬ。式の立て方が想定解と違う方法かもだけど、通ったのでメモ。

xが小さいときを考える。
dp[i]:=距離がiであるような頂点数
を考えて、dp[0]〜dp[x]の和が答えになる。
が、2段階計算しないといけない、かつ、xが大きくなりすぎるため、無理。

dp[i]:=距離がi以下であるような頂点数
を考えると、実は、距離がxである頂点数=dp[x]-dp[x-1]で求められるので、
dp[i]=(距離がiである頂点数)+(距離がi-1以下である頂点数)
=Σ(距離がi-d[j]である頂点数) + dp[i-1]
=Σ(dp[i-d[j ] ] - dp[i-d[j ]-1 ] ) + dp[i-1]
となり、i-d[j]は高々100程度なので、dp[i]をdp[i-1]からdp[i-100]までの値を使って求めることができる。

漸化式で求めることができたので、行列累乗を使って高速に求められる。
(dp[101],...,dp[1])^T = A * (dp[100],...,dp[0])^T
となるような行列Aを考えると、2行以降は単純に値をそのまま渡せばいいので、
1 0 .... 0
0 1 .... 0
...
0 .... 1 0
のようになる。
1行目は、上の漸化式から、
dp[i-1]の分はA[0][0]の部分が1になり、d[j]に対応して、d[j]番目とd[j]+1番目のところが
1 0 .... 1 -1 .... 0
のようになる。
あとは、
(dp[102],...,dp[2])^T = A^2 * (dp[100],...,dp[0])^T
のようにAの(x-100)乗をかければ答えが求まる。
行列の累乗は繰り返し二乗法でO(N^3*log(x))程度になるので、間に合う。

上記の漸化式も行列も、マイナスがでてくるが、MODを取っているので、MODを足して正の値にしておく必要がある。