数论 单位根反演+扩域 CF1548C题解

· · 题解

数学好久没碰已经不会 GF 咯！

在这里提供一个单反做法。

\sum_{i=0}^{n}\binom{i}{m}[3\mid i] \sum_{i=0}^{n}\binom{i}{m}\frac{1}{3}\sum_{j=0}^{2}w_3^{ij} \frac{1}{3}\sum_{j=0}^{2}\sum_{i=0}^{n}\binom{i}{m}(w_3^j)^i F_j[m]=\sum_{i=0}^{n}\binom{i}{m}(w_3^j)^i F_j[m]=\sum_{i=0}^{n}(\binom{i-1}{m}+\binom{i-1}{m-1})(w_3^j)^i F_j[m]=w_3^j(\sum_{i=0}^{n-1}\binom{i}{m}(w_3^j)^i+\sum_{i=0}^{n-1}\binom{i}{m-1}(w_3^j)^i) F_j[m]=w_3^j(F_j[m]-\binom{n}{m}w_3^{nj}+F_j[m-1]-\binom{n}{m-1}w_3^{nj}) F_j[m]=w_3^j(F_j[m]+F_j[m-1]-\binom{n+1}{m}w_3^{nj}) F_j[m]=\frac{w_3^jF_j[m-1]-\binom{n+1}{m}w_3^{(n+1)j}}{1-w_3^j}

根据题意这里有 3\mid n。

F_j[m]=\frac{w_3^jF_j[m-1]-\binom{n+1}{m}w_3^j}{1-w_3^j} F_j[m]=\frac{w_3^j}{1-w_3^j}\times(F_j[m-1]-\binom{n+1}{m})

记 w_3^0=1,w_3^1=x,w_3^2=x^2，然后将单位根看做多项式做长度为 3 的循环卷积即可。（这里 x=\frac{\sqrt{3}i-1}{2},x^2=\frac{-\sqrt{3}i-1}{2}）

求逆元？

你可以手搓逆元，但是得根据 x 的意义来搓。

也就是说不可能凑出来 1+0x+0x^2，只能凑出来 a+bx+cx^2 满足 a-\frac{b+c}{2}=1 且 b=c。

设 (1-x)\times(t_0+t_1x+t_2x^2)=a+bx+bx^2。

其实只需要凑出来 b=c 就行了。。。第一个限制可以通过除以一个常数来解决。

那么就是 a=t_0-t_2,b=t_1-t_0=t_2-t_1

只需要满足 2\times a\neq b+c 就行了

可以得到一组解是 $t_0=0,t_1=1,t_2=2$。 此时 $(1-x)(x+2x^2)=-2+x+x^2,a-\frac{b+c}{2}=-3

所以逆元是 -\frac{1}{3}x-\frac{2}{3}x^2。

同理可得 -\frac{2}{3}x-\frac{1}{3}x^2 是 1-x^2 的逆元。

复杂度 O(n3^3)，应该是可以过去的。需要注意 j=0 的时候 F 的值是一个组合数

听说好像有 O(n3^2) 的简单 GF 做法。果然还是我太菜了。

ans_x=\frac{F_0[x]+F_1[x]+F_2[x]}{3} 
#include<cstdio>
typedef unsigned ui;
typedef unsigned long long ull;
const ui M=3e6+5,inv3=333333336,mod=1e9+7;
ui n,q,F0[M],fac[M],ifac[M];
struct poly{
    ui f0,f1,f2;
    poly(const ui&f0=0,const ui&f1=0,const ui&f2=0):f0(f0),f1(f1),f2(f2){}
    inline ui&operator[](const ui&x){
        return x==0?f0:x==1?f1:f2;
    }
    inline poly operator*(const ui&x)const{
        return poly(1ull*f0*x%mod,1ull*f1*x%mod,1ull*f2*x%mod);
    }
    inline poly operator+(const poly&g)const{
        return poly((f0+g.f0)%mod,(f1+g.f1)%mod,(f2+g.f2)%mod);
    }
    inline poly operator-(const poly&g)const{
        return poly((f0+mod-g.f0)%mod,(f1+mod-g.f1)%mod,(f2+mod-g.f2)%mod);
    }
    inline poly operator*(poly g){
        ull ans[3];ans[0]=ans[1]=ans[2]=0;
        for(ui i=0;i^3;++i)for(ui j=0;j^3;++j)ans[i+j>=3?i+j-3:i+j]+=1ull*(*this)[i]*g[j];
        return poly(ans[0]%mod,ans[1]%mod,ans[2]%mod);
    }
}c,F1[M],F2[M];
inline ui C(const ui&n,const ui&m){
    return 1ull*ifac[m]*ifac[n-m]%mod*fac[n]%mod;
}
inline poly pow(poly a,ull b){
    poly ans(1);for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;
}
inline ui pow(ui a,ui b){
    ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;
}
signed main(){
    scanf("%u%u",&n,&q);n*=3;fac[0]=fac[1]=ifac[0]=ifac[1]=1;
    for(ui i=2;i<=n+1;++i)fac[i]=1ull*fac[i-1]*i%mod,ifac[i]=1ull*(mod-mod/i)*ifac[mod%i]%mod;
    for(ui i=2;i<=n+1;++i)ifac[i]=1ull*ifac[i]*ifac[i-1]%mod;
    for(ui i=0;i<=n;++i)F0[i]=C(n+1,i+1);
    c=poly(0,1,0)*poly(0,mod-inv3,(mod-2ull)*inv3%mod);
    F1[0]=poly(1,0,0);for(ui i=1;i<=n;++i)F1[i]=c*(F1[i-1]-C(n+1,i));
    c=poly(0,0,1)*poly(0,(mod-2ull)*inv3%mod,mod-inv3);
    F2[0]=poly(1,0,0);for(ui i=1;i<=n;++i)F2[i]=c*(F2[i-1]-C(n+1,i));
    while(q--){
        ui x;scanf("%u",&x);
        poly ans=poly(F0[x])+F1[x]+F2[x];
        printf("%u\n",(ans.f0+500000003ull*(ans.f1+ans.f2))%mod*inv3%mod);
    }
}