ヒント1 : FMTは使わない(MODが変な意味はない)
ヒント2 : 式の形は、個数に対応するハッシュではなく意味がある
ScannerとModIntは、多分大体想像通りの挙動です
import std.stdio, std.conv, std.typecons;
import dcomp.scanner;
import dcomp.numeric.modint;
alias Mint = ModInt!1224736769;
alias Edge = Tuple!(int, "to", Mint, "data");
int main() {
auto sc = new Scanner();
int n, buf;
sc.read(n, buf);
Mint M = Mint(buf);
int[] t = new int[n];
int[] x = new int[n];
Edge[][] g = new Edge[][](n);
int co = 0;
int[] pos = new int[n];
foreach(i; 0..n) {
sc.read(t[i], x[i]);
if (t[i] == 1) {
pos[i] = co; co++;
if (i) {
g[pos[i-1]] ~= Edge(pos[i], Mint(x[i]));
}
} else {
pos[i] = pos[x[i]-1];
}
}
Mint[] res = new Mint[](n);
void dfs(int p, Mint a, Mint[2][5] X) {
Mint[5] nw;
nw[4] = (Mint(1)+X[4][0]+X[4][1])*M;
nw[3] = nw[4] + (X[3][0]+X[3][1])*M;
nw[2] = a*nw[4] + (X[2][0]+X[2][1])*M;
nw[1] = a*nw[3] + (X[1][0]+X[1][1]+X[2][0]+X[2][1])*M;
nw[0] = X[0][0] + nw[1];
res[p] = nw[0];
Mint[2][5] next;
foreach (i; 0..5) {
next[i][0] = nw[i];
next[i][1] = X[i][0];
}
foreach (e; g[p]) {
dfs(e.to, e.data, next);
}
}
dfs(0, Mint(x[0]), (Mint[2][5]).init);
foreach (i; 0..n) {
writeln(res[pos[i]]);
}
return 0;
}
おまけ
解法があってるかは未検証です。
ヒント1 : 係数がどうしようもなくなったので、長さごとにその長さの数列たちの和を独立に計算します
ヒント2 : 「長さ200,000の数列(各要素は109とか)を全部かけてください、ただしModではなく多倍長でそのまま」 を普通に順番に掛けるより早く計算するにはどうする?
SegTreeの形に分解して、葉から計算していきます。
各ノードには、左2個と右2個の使用状況と数列の長さをキーにして、数列たちの個数と総和をもたせます。
count[4][4][1..size+1]とsum[4][4][1..size+1]みたいなイメージ
これらは子の要素に対して適当に
FFTすれば計算できるはず