maroonさんのお正月問題 - よすぽの日記

あけましておめでとうございます！
↓はお正月問題のリンクです。
新年早々重い問題を解きたい方はぜひやってみてください。https://t.co/GH0VwifmvK
— 最高の夏 (@maroon_kuri) January 1, 2017

ヒント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) { //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;
}

おまけ

@maroon_kuri そういえば、

長さ200,000ぐらいの数列MとCが与えられるのでG(M)を求めよ、ただしF=|A|*M^|A|*sum(A_i)ではなく、F=C_|A| * sum(A_i)、クエリはなし

という問題が思考過程で生成されました(逆出題)
— yosupo (@yosupot) 2017年1月3日

@maroon_kuri 要するにクエリがなくなった代わりにFがより複雑になったバージョンです
— yosupo (@yosupot) 2017年1月3日

解法があってるかは未検証です。

ヒント1 : 係数がどうしようもなくなったので、長さごとにその長さの数列たちの和を独立に計算します

ヒント2 : 「長さ200,000の数列(各要素は10⁹とか)を全部かけてください、ただしModではなく多倍長でそのまま」を普通に順番に掛けるより早く計算するにはどうする？

解法