警示后人，如果你WA45pts

并且是测试点 #1,#6->#15 WA，

那么检查一下，你做 NTT 的时候

N

的大小有没有开够 QwQ

CPP

    void convolution(vector<int>& a,vector<int> c){
        prework(a.size()*2);/*prework(a.size()+c.size()+1)*/
        int tmp=a.size();
        a.resize(N),c.resize(N);
        NTT(a,0),NTT(c,0);
        for(int i=0;i<N;i++) a[i]=mul(c[i],pls(2,mod-mul(a[i],c[i])));
        NTT(a,1);
        a.resize(tmp);
    }

解释一下，prework(n) 中的

n

是 NTT 要处理的数组长度，之后会转化成

2

的幂，

a

是传进去的

F(x)

，

c

是

G_1(x)

，函数返回

G(x)

。

这里之所以要开成

2n

的点值，是因为

G_1(x)(2-F(x)G_1(x))

最高次幂可能是

2n

级别的，点值一定要开够，再对

x^n

取模。

另外推荐大家用 std::vector，虽说常数大概是数组的两倍，但是这种写法几乎没有细节：

CPP

vector<int> PolyInv(vector<int> a){
    if(a.size()==1u){
        a[0]=inv(a[0]);
        return a;
    }
    vector<int> b((a.size()+1)>>1);
    for(int i=0;i<(int)b.size();i++) b[i]=a[i];
    b=PolyInv(b);
    ntt::convolution(a,b);
    return a;
}

警示后人，如果你WA45pts

讨论操作

回复

相关推荐

警示后人，如果你WA45pts