2022杭电多校六1003 hdoj7199 Find the Number of Paths

设为已经走了步，当前在点的方案数，易知方程为

式子不太方便，考虑令新标号等于原标号 则式子变为

考虑生成函数形式，设为所对应的生成函数 则

根据高中知识，构造 则

就可以快速求出和

时间复杂度，但常数巨大

主函数核心代码就十行

int main()
{
    int p, q, u, v, w, x, y, z, T;
    cin >> T;
    while (T--)
    {
        scanf("%d%d", &n, &k);
        poly A(n);
        for (int i = 1; i <= n - 1; i++)
            scanf("%lld", &A[i]);
        poly F = A.integ().exp(k + 1);
        poly G0 = F << (n - 1);
        poly Gk(n);
        for (int i = 0; i < n; i++)
            Gk[i] = G0[i + k] * fac[i + k] % mod * ifac[i] % mod;
        poly H = Gk * F.inv(n);
        for (int i = n - 1; i >= 0; i--)
            printf("%lld%c", H[i], " \n"[i == 0]);
    }
    return 0;
}