maroonさんのお正月問題

ソースコード

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) { //S,A,B,C,D 
        Mint[5] nw;
        nw[4] = (Mint(1)+X[4][0]+X[4][1])*M; // D
        nw[3] = nw[4] + (X[3][0]+X[3][1])*M; // C
        nw[2] = a*nw[4] + (X[2][0]+X[2][1])*M; // B
        nw[1] = a*nw[3] + (X[1][0]+X[1][1]+X[2][0]+X[2][1])*M; // A
        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;
}

解法

SegTreeの形に分解して、葉から計算していきます。 各ノードには、左2個と右2個の使用状況と数列の長さをキーにして、数列たちの個数と総和をもたせます。 count[4][4][1..size+1]とsum[4][4][1..size+1]みたいなイメージ これらは子の要素に対して適当にFFTすれば計算できるはず