蒟蒻求助exp
查看原帖
蒟蒻求助exp
134519
qwq自动机楼主2021/9/26 17:58

rt,求逆 / ln / NTT 写的都是对的(从模板里搞下来的),但是过不了样例 /fad

现在怀疑是 exp 的问题 qwq

有人能帮我看看我的 exp 哪里写炸了吗 /kel

void pExp(ll *f, ll *res, int n)
{
    static ll tmp1[MAXN << 2], tmp2[MAXN << 2], tmp3[MAXN << 2];
    res[0] = 1;
    for (int l = 2; l <= n; l <<= 1)
    {
        for (int i = 0; i < l; i++)
            tmp1[i] = tmp2[i] = res[i], tmp3[i] = f[i];
        for (int i = l; i < l << 1; i++)
            tmp1[i] = tmp2[i] = tmp3[i] = 0;
        NTT(tmp3, l << 1);
        Ln(tmp2, l << 1);
        NTT(tmp1, l << 1);
        NTT(tmp2, l << 1);
        for (int i = 0; i < l << 1; i++)
            tmp1[i] = tmp1[i] * ((1 - tmp2[i]) % MOD + MOD + tmp3[i] % MOD) % MOD;
        NTT(tmp1, l << 1, true);
        for (int i = 0; i < l; i++)
            res[i] = tmp1[i];
    }
}
2021/9/26 17:58
加载中...