XCPC Notes

Appearance

发布时间：2024-09-28

FFT ​

  • 任一n个点就可以确定n-1元一次方程
  • 系数表达式->点表达式->系数表达式
  • 系数表达式->点表达式
    • A(x)=a0+a1x+a2x2+....+an−1xn−1A(x)=a_0+a_1x+a_2x^2+....+a_{n-1}x^{n-1}
    • A1(x)=a0+a2x2+an−2xn2−1A_1(x)=a_0+a_2x^2+a_{n-2}x^{\frac{n}{2}-1}
    • A2(x)=a1+a3x+...+an−1xn2−1A_2(x)=a_1+a_3x+...+a_{n-1}x^{\frac{n}{2}-1}
    • A(x)=A1(x2)+xA2(x2)A(x)=A_1(x^2)+xA_2(x^2)
    • k∈[0,n2−1],A(ωnk)=A1(ωn2k)+ωnkA2(ωn2k)k∈[0,\frac{n}{2}-1],A(\omega _n^k)=A_1(\omega _{\frac{n}{2}}^k)+\omega _n^kA_2(\omega _{\frac{n}{2}}^k)
    • k∈[n2,n−1],A(ωnk)=A1(ωn2k)−ωnkA2(ωn2k)k∈[\frac{n}{2},n-1],A(\omega _n^k)=A_1(\omega _{\frac{n}{2}}^k)-\omega _n^kA_2(\omega _{\frac{n}{2}}^k)
  • 点表达式->系数表达式
    • A(x)=C0+C1x+C2x2+Cn−1xn−1A(x)=C_0+C_1x+C_2x^2+C_{n-1}x^{n-1}
    • yk=A(ωnk),Ck=∑i=0n−1yi(ωn−k)iy_k=A(\omega _n^k),C_k=\sum _{i=0}^{n-1}y_i(\omega _n^{-k})^i
    • B(x)=y0+y1x+...+yn−1xn−1B(x)=y_0+y_1x+...+y_{n-1}x^{n-1}
    • Ck=B(ωn−k)C_k=B(\omega _n^{-k})
    • ak=Ckna_k=\frac{C_k}{n}
cpp
const double PI=acos(-1.0);
struct Complex{
    double x,y;
    Complex(double x=0,double y=0):x(x),y(y){}
    Complex operator +(const Complex &t)const{
        return {x+t.x,y+t.y};
    }
    Complex operator -(const Complex &t)const{
        return {x-t.x,y-t.y}; 
    }
    Complex operator *(const Complex &t)const{
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
} a[N],b[N];
int rev[N],bit,tot;
void fft(Complex a[],int inv){
    for(int i=0;i<tot;i++){
        if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int mid=1;mid<tot;mid<<=1){
        Complex w1(cos(PI/mid),inv*sin(PI/mid));
        for(int i=0;i<tot;i+=mid*2){
            Complex wk(1,0);
            for(int j=0;j<mid;j++,wk=wk*w1){
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)cin>>a[i].x;
    for(int i=0;i<=m;i++)cin>>b[i].x;
    while((1ll<<bit)<n+m+1)bit++;
    tot=1ll<<bit;
    for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,1),fft(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=0;i<=n+m;i++)a[i].x/=tot;
    for(int i=0;i<=n+m;i++)cout<<(int)(a[i].x+0.5)<<" ";
}

高精度乘法 ​

cpp
const double PI=acos(-1.0);
struct Complex{
    double x,y;
    Complex(double x=0,double y=0):x(x),y(y){}
    Complex operator +(const Complex &t)const{
        return {x+t.x,y+t.y};
    }
    Complex operator -(const Complex &t)const{
        return {x-t.x,y-t.y}; 
    }
    Complex operator *(const Complex &t)const{
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
};
int rev[N],bit,tot;
void fft(vector<Complex> &a,int inv){
    for(int i=0;i<tot;i++){
        if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int mid=1;mid<tot;mid<<=1){
        Complex w1(cos(PI/mid),inv*sin(PI/mid));
        for(int i=0;i<tot;i+=mid*2){
            Complex wk(1,0);
            for(int j=0;j<mid;j++,wk=wk*w1){
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
}
vector<int> mul(vector<int> &A,vector<int> &B){
    vector<Complex> a,b;
    int n=A.size()-1,m=B.size()-1;
    for(int i=0;i<=n;i++)a.push_back(A[i]);
    for(int i=0;i<=m;i++)b.push_back(B[i]);
    while((1<<bit)<n+m+1)bit++;
    tot=1<<bit;
    while(a.size()<tot)a.push_back(0);
    while(b.size()<tot)b.push_back(0);
    for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,1),fft(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
    fft(a,-1);
    vector<int> C;
    for(int i=0,t=0;i<tot||t;i++){
        if(i<tot)t+=(int)(a[i].x/tot+0.5);
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}
void solve(){
    string s,t;
    cin>>s>>t;
    vector<int> A,B;
    for(int i=s.size()-1;i>=0;i--)A.push_back(s[i]-'0');
    for(int i=t.size()-1;i>=0;i--)B.push_back(t[i]-'0');
    auto ans=mul(A,B);
    for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
}

NTT ​

单位根换原根即可

固定模数板子 ​

cpp
namespace NTT{
    vector<int> rev;
    int bit=0,tot,g=3,gi;
    const int P=998244353;
    int qpow(int a,int b){
        int ans=1;
        for(;b;b>>=1){
            if(b&1)ans=ans*a%P;
            a=a*a%P;
        }
        return ans;
    }
    int inv(int n){
        return qpow(n,P-2);
    }
    void ntt(vector<int> &a,int inv){
        for(int i=0;i<tot;i++){
            if(i<rev[i])swap(a[i],a[rev[i]]);
        }
        for(int mid=1;mid<tot;mid<<=1){
            int g1=qpow(inv==1?g:gi,(P-1)/(mid*2));
            for(int i=0;i<tot;i+=mid*2){
                int gk=1;
                for(int j=0;j<mid;j++,gk=gk*g1%P){
                    auto x=a[i+j],y=gk*a[i+j+mid]%P;
                    a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
                }
            }
        }
        if(inv==-1){
            int invn=NTT::inv(tot);
            for(int i=0;i<tot;i++)a[i]=a[i]*invn%P;
        }
    }
    void init(int n){
        while((1<<bit)<n)bit++;
        tot=1<<bit;
        rev.resize(tot);
        for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        gi=inv(g);
    }
    void mul(vector<int> &a,vector<int> &b,int n,int m){
        init(n+m+1);
        a.resize(tot),b.resize(tot);
        ntt(a,1),ntt(b,1);
        for(int i=0;i<tot;i++)a[i]=a[i]*b[i]%P;
        ntt(a,-1);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1),b(m+1);
    for(int i=0;i<=n;i++)cin>>a[i];
    for(int i=0;i<=m;i++)cin>>b[i];
    NTT::mul(a,b,n,m);
    for(int i=0;i<=n+m;i++)cout<<a[i]<<" ";
}

常见NTT模数 ​

r*2^k+1                        r                            k                            g
3                              1                            1                            2
5                              1                            2                            2
17                             1                            4                            3
97                             3                            5                            5
193                            3                            6                            5
257                            1                            8                            3
7681                           15                           9                            17
12289                          3                            12                           11
40961                          5                            13                           3
65537                          1                            16                           3
786433                         3                            18                           10
5767169                        11                           19                           3
7340033                        7                            20                           3
23068673                       11                           21                           3
104857601                      25                           22                           3
167772161                      5                            25                           3
469762049                      7                            26                           3
998244353                      119                          23                           3
1004535809                     479                          21                           3
2013265921                     15                           27                           31
2281701377                     17                           27                           3
3221225473                     3                            30                           5
75161927681                    35                           31                           3
77309411329                    9                            33                           7
206158430209                   3                            36                           22
2061584302081                  15                           37                           7
2748779069441                  5                            39                           3
6597069766657                  3                            41                           5
39582418599937                 9                            42                           5
79164837199873                 9                            43                           5
263882790666241                15                           44                           7
1231453023109121               35                           45                           3
1337006139375617               19                           46                           3
3799912185593857               27                           47                           5
4222124650659841               15                           48                           19
7881299347898369               7                            50                           6
31525197391593473              7                            52                           3
180143985094819841             5                            55                           6
1945555039024054273            27                           56                           5
4179340454199820289            29                           57                           3

高精度乘法NTT板子 ​

cpp
namespace NTT{
    const int P=998244353;
    int rev[N],bit=0,tot,g=3,gi;
    int qpow(int a,int b){
        int ans=1;
        for(;b;b>>=1){
            if(b&1)ans=ans*a%P;
            a=a*a%P;
        }
        return ans;
    }
    int inv(int n){
        return qpow(n,P-2);
    }
    void ntt(vector<int> &a,int inv){
        for(int i=0;i<tot;i++){
            if(i<rev[i])swap(a[i],a[rev[i]]);
        }
        for(int mid=1;mid<tot;mid<<=1){
            int g1=qpow(inv==1?g:gi,(P-1)/(mid*2));
            for(int i=0;i<tot;i+=mid*2){
                int gk=1;
                for(int j=0;j<mid;j++,gk=gk*g1%P){
                    auto x=a[i+j],y=gk*a[i+j+mid]%P;
                    a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
                }
            }
        }
    }
    void init(int n){
        while((1<<bit)<n)bit++;
        tot=1<<bit;
        for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        gi=inv(g);
    }
}
vector<int> mul(vector<int> &A,vector<int> &B){
    vector<int> a,b;
    int n=A.size()-1,m=B.size()-1;
    for(int i=0;i<=n;i++)a.push_back(A[i]);
    for(int i=0;i<=m;i++)b.push_back(B[i]);
    NTT::init(n+m+1);
    int tot=NTT::tot;
    while(a.size()<tot)a.push_back(0);
    while(b.size()<tot)b.push_back(0);
    NTT::ntt(a,1),NTT::ntt(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i]%NTT::P;
    NTT::ntt(a,-1);
    int inv=NTT::inv(tot);
    for(int i=0;i<tot;i++)a[i]=a[i]*inv%NTT::P;
    vector<int> C;
    for(int i=0,t=0;i<tot||t;i++){
        if(i<tot)t+=a[i];
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}
void solve(){
    string s,t;
    cin>>s>>t;
    vector<int> A,B;
    for(int i=s.size()-1;i>=0;i--)A.push_back(s[i]-'0');
    for(int i=t.size()-1;i>=0;i--)B.push_back(t[i]-'0');
    auto ans=mul(A,B);
    for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
}

任意模数NTT(MTT) ​

三模数NTT ​

假设答案为x，三模数分别为A,B,C

  • x≡x1(mod A)x \equiv x_1(mod\ A)
  • x≡x2(mod B)x \equiv x_2(mod\ B)
  • x≡x3(mod C)x \equiv x_3(mod\ C)

合并前两个，

  • x1+k1A=x2+k2Bx_1+k_1A=x_2+k_2B
  • x1+k1A≡x2(mod B)x_1+k_1A \equiv x_2(mod\ B)
  • k1≡x2−x1A(mod B)k1 \equiv \frac{x_2-x_1}{A}(mod\ B)

求出 x≡x1+k1A(mod AB),x4=x1+k1A(mod AB)x \equiv x_1+k_1A(mod\ AB),x_4=x_1+k_1A(mod\ AB)

  • x4+k4AB=x3+k3Cx_4+k_4AB=x_3+k_3C
  • k4≡x3−x4AB(mod C)k_4 \equiv \frac{x_3-x_4}{AB}(mod\ C)

求出 x≡x4+k4AB(mod ABC),x<ABC,x=x4+k4ABx \equiv x_4+k_4AB(mod\ ABC),x<ABC,x=x_4+k_4AB

cpp
namespace NTT{
    vector<int> rev;
    int bit=0,tot;
    int qpow(int a,int b,const int mod){
        int ans=1;
        for(;b;b>>=1){
            if(b&1)ans=ans*a%mod;
            a=a*a%mod;
        }
        return ans;
    }
    int inv(int n,int P){
        return qpow(n,P-2,P);
    }
    const int mod1=998244353,mod2=1004535809,mod3=469762049,g=3;
    const int mod1_2=mod1*mod2;
    const int inv1=inv(mod1,mod2),inv2=inv(mod1_2%mod3,mod3);
    struct Int{
        int A,B,C;
        Int(){}
        Int(int val):A(val),B(val),C(val){}
        Int(int _A,int _B,int _C):A(_A),B(_B),C(_C){}
        static Int reduce(const Int &x){
            return Int(x.A+(x.A>>31&mod1),x.B+(x.B>>31&mod2),x.C+(x.C>>31&mod3));
        }
        Int operator + (const Int &t)const{
            return reduce(Int(A+t.A-mod1,B+t.B-mod2,C+t.C-mod3));
        }
        Int operator - (const Int &t)const{
            return reduce(Int(A-t.A,B-t.B,C-t.C));
        }
        Int operator * (const Int &t)const{
            return {A*t.A%mod1,B*t.B%mod2,C*t.C%mod3};
        }
        int val(){
            int x=(B-A+mod2)%mod2*inv1%mod2*mod1+A;
            return ((C-x%mod3+mod3)%mod3*inv2%mod3*(mod1_2%P)%P+x)%P;
        }
    } itot;
    vector<Int> gn;
    void ntt(vector<Int> &a,int inv){
        for(int i=1;i<tot;i++){
            if(i<rev[i])swap(a[i],a[rev[i]]);
        }
        for(int mid=1;mid<tot;mid<<=1){
            const int t=tot/mid>>1;
            for(int i=0;i<tot;i+=mid*2){
                for(int j=0;j<mid;j++){
                    const Int gk=(inv==1?gn[t*j]:gn[tot-t*j]);
                    const Int x=a[i+j],y=gk*a[i+j+mid];
                    a[i+j]=x+y,a[i+j+mid]=x-y;
                }
            }
        }
        if(inv==-1){
            for(int i=0;i<tot;i++)a[i]=a[i]*itot;
        }
    }
    void init(int n){
        bit=0;
        while((1<<bit)<n)bit++;
        tot=1<<bit;
        itot={inv(tot,mod1),inv(tot,mod2),inv(tot,mod3)};
        rev.resize(tot);
        gn.resize(tot+1);
        const Int t={qpow(g,(mod1-1)/tot,mod1),qpow(g,(mod2-1)/tot,mod2),qpow(g,(mod3-1)/tot,mod3)};
        gn[0]=Int(1);
        for(int i=0;i<tot;i++){
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
            gn[i+1]=gn[i]*t;
        }
    }
    void mul(vector<Int> &a,vector<Int> &b,int n,int m){
        init(n+m+1);
        a.resize(tot,Int(0));
        b.resize(tot,Int(0));
        ntt(a,1),ntt(b,1);
        for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
        ntt(a,-1);
    }
}
using NTT::Int;
void solve(){
    int n,m;
    cin>>n>>m>>P;
    vector<Int> a(n+1),b(m+1);
    for(int i=0;i<=n;i++){
        int x;
        cin>>x;
        a[i]=Int(x%P);
    }
    for(int i=0;i<=m;i++){
        int x;
        cin>>x;
        b[i]=Int(x%P);
    }
    NTT::mul(a,b,n,m);
    for(int i=0;i<=n+m;i++)cout<<a[i].val()<<" ";
}

FWT ​

或运算 ​

  1. 正向变换
    • FWT[A]i=∑i=i∣jAjFWT[A]_i=\sum_{i=i|j}A_j，即jj是ii的二进制子集
    • FWT[A]i⋅FWT[B]i=(∑i=i∣jAj)(∑i=i∣kAk)=∑i∣(j∣k)=iAjAk=FWT[C]iFWT[A]_i \cdot FWT[B]_i=(\sum_{i=i|j}A_j)(\sum_{i=i|k}A_k)=\sum_{i|(j|k)=i}A_jA_k=FWT[C]_i
    • 分治法计算FWT[A]FWT[A]，那么记A0A_0为区间前半部分子集，A1A_1为区间后半部分
    • 有FWT[A]=merge(FWT[A0],FWT[A0]+FWT[A1])FWT[A]=merge(FWT[A_0],FWT[A_0]+FWT[A_1])，只考虑最高位，最高位为0的子集就是自己，最高位为1的子集，可以拆分为强制为0或1
  2. 逆向变换
    • IFWT[A]=merge(IFWT[A0],IFWT[A1]−IFWT[A0])IFWT[A]=merge(IFWT[A_0],IFWT[A_1]-IFWT[A_0])
    • 感性证明，注意下标：
    • FWT[A]0=FWT[A0],FWT[A]1=FWT[A0]+FWT[A1]FWT[A]_0=FWT[A_0],FWT[A]_1=FWT[A_0]+FWT[A_1]
    • FWT[A1]=FWT[A]1−FWT[A0]=FWT[A]1−FWT[A]0FWT[A_1]=FWT[A]_1-FWT[A_0]=FWT[A]_1-FWT[A]_0Ci=∑j⊕kAjBkC_i = \sum_{j \oplus k} A_jB_k
  • or:FWT[A]i=∑i∣j=iAjor:FWT[A]_i=\sum_{i|j=i}A_j，本质是高维前缀和
    • 正变换：FWT[A]=(FWT[A0],FWT[A0+A1])FWT[A]=(FWT[A_0],FWT[A_0+A_1])
    • 逆变换：IFWT[A]=(IFWT[A0],IFWT[A1−A0])IFWT[A]=(IFWT[A_0],IFWT[A_1-A_0])
  • and:FWT[A]i=∑i&j=iAjand:FWT[A]_i=\sum_{i\&j=i}A_j，本质是高维后缀和
    • 正变换：FWT[A]=(FWT[A0+A1],FWT[A1])FWT[A]=(FWT[A_0+A_1],FWT[A_1])
    • 逆变换：IFWT[A]=(IFWT[A0−A1],IFWT[A1])IFWT[A]=(IFWT[A_0-A_1],IFWT[A_1])
  • xor:FWT[A]i=∑j(−1)popcount(i&j)Ajxor:FWT[A]_i=\sum_j (-1)^{popcount(i\&j)}A_j
    • 正变换：FWT[A]=(FWT[A0+A1],FWT[A0−A1])FWT[A]=(FWT[A_0+A_1],FWT[A_0-A_1])
    • 逆变换：IFWT[A]=(IFWT[A0+A1]2,IFWT[A0−A1]2)IFWT[A]=(\frac{IFWT[A_0+A_1]}{2},\frac{IFWT[A_0-A_1]}{2})
cpp
namespace FWT{
    static constexpr int mod=998244353;
    static constexpr int inv2=(mod+1)/2;
    int n;
    void fwt_or(vector<int> &a,int op=1){
        for(int x=2;x<=n;x<<=1){
            int k=x>>1;
            for(int i=0;i<n;i+=x){
                for(int j=0;j<k;j++){
                    a[i+j+k]+=a[i+j]*op%mod;
                    a[i+j+k]%=mod;
                }
            }
        }
    }
    void fwt_and(vector<int> &a,int op=1){
        for(int x=2;x<=n;x<<=1){
            int k=x>>1;
            for(int i=0;i<n;i+=x){
                for(int j=0;j<k;j++){
                    a[i+j]+=a[i+j+k]*op%mod;
                    a[i+j]%=mod;
                }
            }
        }
    }
    void fwt_xor(vector<int> &a,int op=1){
        for(int x=2;x<=n;x<<=1){
            int k=x>>1;
            for(int i=0;i<n;i+=x){
                for(int j=0;j<k;j++){
                    int X=a[i+j],Y=a[i+j+k];
                    a[i+j]=(X+Y)*op%mod;
                    a[i+j+k]=(X-Y+mod)%mod*op%mod;
                }
            }
        }
    }
    // 同或
    void fwt_xnor(vector<int> &a,int op){
        for(int x=2;x<=n;x<<=1){
            int k=x>>1;
            for(int i=0;i<n;i+=x){
                for(int j=0;j<k;j++){
                    int X=a[i+j],Y=a[i+j+k];
                    a[i+j+k]=(X+Y)*op%mod;
                    a[i+j]=(X-Y+mod)%mod*op%mod;
                }
            }
        }
    }
    void ifwt_or(vector<int> &a){
        fwt_or(a,mod-1);
    }
    void ifwt_and(vector<int> &a){
        fwt_and(a,mod-1);
    }
    void ifwt_xor(vector<int> &a){
        fwt_xor(a,inv2);
    }
    void ifwt_xnor(vector<int> &a){
        fwt_xnor(a,inv2);
    }
    void init(int m){
        for(n=1;n<=m;n<<=1);
    }
}

FWT求三个集合异或的不同个数 ​

复杂度O(Vlog⁡V)O(V \log V)

cpp
class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int mx=*max_element(nums.begin(),nums.end());
        init(mx);
        vector<long long> A(n),B(n);
        for(auto x:nums)A[x]=1,B[x]=1;
        fwt_xor(A);
        for(int i=0;i<n;i++)A[i]=A[i]*A[i]%mod;
        fwt_xor(B);
        for(int i=0;i<n;i++)A[i]=A[i]*B[i]%mod;
        ifwt_xor(A);
        int ans=0;
        for(int i=0;i<n;i++){
            if(A[i])ans++;
        }
        return ans;
    }
};

子集卷积 ​

  • Ck=∑i&j=0,i∣j=kAjBkC_{k}= \sum_{i \& j=0,i|j=k}A_jB_k
  • 定义Cx,sC_{x,s}表示ss的集合中，11的个数是xx
  • 复杂度O(nlog⁡2n)O(n \log^2n)
cpp
void solve(){
    int m;
    cin>>m;
    n=1<<m;
    vector<int> A(n),B(n);
    vector a(21,vector<int>(n)),b(21,vector<int>(n)),c(21,vector<int>(n));
    for(int i=0;i<n;i++)cin>>A[i],a[__builtin_popcount(i)][i]=A[i];
    for(int i=0;i<n;i++)cin>>B[i],b[__builtin_popcount(i)][i]=B[i];
    for(int i=0;i<21;i++)fwt_or(a[i]),fwt_or(b[i]);
    for(int x=0;x<21;x++){
        for(int i=0;i<=x;i++){
            for(int j=0;j<n;j++){
                c[x][j]+=a[i][j]*b[x-i][j]%mod;
                c[x][j]%=mod;
            }
        }
        ifwt_or(c[x]);
    }
    for(int i=0;i<n;i++)cout<<c[__builtin_popcount(i)][i]<<" ";
}

CF383E Vowels ​

给出n个长度为3的由′a′~′x′组成的单词，一个单词是正确的当且仅当其包含至少一个元音字母。 这里的元音字母是a-x的一个子集。 对于所有元音字母集合，求这n个单词中正确单词的数量平方的异或和。

  • 正难则反，设dpidp_i表示辅音字母集合的数量
  • sosdp
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> dp(1<<24);
    for(int i=1;i<=n;i++){
        int mask=0;
        for(int j=1;j<=3;j++){
            char c;
            cin>>c;
            if(c>='y')continue;
            mask|=1<<(c-'a');
        }
        dp[mask]++;
    }
    FWT::n=1<<24;
    FWT::fwt_or(dp);
    int ans=0;
    for(int i=0;i<1<<24;i++)ans^=(n-dp[i])*(n-dp[i]);
    cout<<ans<<"\n";
}

CF449D ​

给一个数组，求出子集and和为0的方案数

  1. 解法一：
    • 设fif_i表示and和恰好为ii的方案数
    • 但是不好求，设gig_i为ii的超集的个数，然后and和为ii的超集的方案数为hi=2gi−1h_i=2^{g_i}-1
    • hi=∑i&j=ifjh_i =\sum_{i\&j=i}f_j
    • 做一个高维差分就可以得到ff
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1),dp(1<<21);
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[a[i]]++;
    }
    for(int i=0;i<21;i++){
        for(int j=0;j<(1<<21);j++){
            if(j&(1<<i)){
                (dp[j^(1<<i)]+=dp[j])%=mod;
            }
        }
    }
    for(int i=0;i<1<<21;i++)dp[i]=qpow(2,dp[i])-1;
    for(int i=0;i<21;i++){
        for(int j=0;j<(1<<21);j++){
            if(j&(1<<i)){
                (dp[j^(1<<i)]+=mod-dp[j])%=mod;
            }
        }
    }
    cout<<dp[0]<<"\n";
}

  1. 解法2

    • 容斥原理：ans=∑i=0n(−1)i的个数hians=\sum_{i=0}^n(-1)^{i的个数}h_i

  2. 解法3

    • 发现前面的分析是什么，就是FWT的and变换的正变换，再逆回去
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1),dp(1<<21);
    FWT::n=1<<21;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[a[i]]++;
    }
    FWT::fwt_and(dp);
    for(int i=0;i<FWT::n;i++)dp[i]=qpow(2,dp[i])-1;
    FWT::ifwt_and(dp);
    cout<<dp[0]<<"\n";
}

CF914G Sum the Fibonacci ​

长度为nn的数组，五元组(a,b,c,d,e)(a,b,c,d,e)是好的

  1. 1≤a,b,c,d,e≤n1 \leq a,b,c,d,e \leq n
  2. 存在非负整数ii，使得(sa∣sb)&sc&(sd⊕sc)=2i(s_a|s_b)\&s_c\&(s_d \oplus s_c)=2^i
  3. sa&sb=0s_a \& s_b=0
  • 1≤n≤106,1≤si≤2171 \leq n \leq 10^6,1 \leq s_i \leq 2^{17}
  1. 求f(sa∣sb)⋅f(sc)⋅f(sd⊕se)mod  1e9+7f(s_a|s_b) \cdot f(s_c) \cdot f(s_d \oplus s_e) \mod 1e9+7 思路：
  • 假设知道了f(sa∣sb),f(sc),f(sd⊕se)f(s_a|s_b),f(s_c),f(s_d \oplus s_e)，那么做个fwt_and卷积即可
  • 那么接下来分别求这三个数组
  • f(sa∣sb)f(s_a|s_b)，由第三个条件可知，这是一个子集卷积，套板子即可求出，设g(sa∣sb)g(s_a|s_b)为符合的个数，那么f(sa∣sb)=g(sa∣sb)⋅fib(sa∣sb)f(s_a|s_b)=g(s_a|s_b) \cdot fib(s_a|s_b)
  • f(sc)f(s_c)，题目已知，用个桶装起来记个数，然后再乘斐波那契数即可
  • f(sd⊕se)f(s_d \oplus s_e)，异或fwt
  • 记最终数组为FF,那么ans=∑i=017F2ians= \sum_{i=0}^{17}F_{2^i}
  • 复杂度：O(nlog⁡n)O(n \log n)
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> s(n+1),fib(1<<17),B(1<<17),D(1<<17);
    vector A(18,vector<int>(1<<17)),C(18,vector<int>(1<<17));
    for(int i=1;i<=n;i++){
        cin>>s[i];
        A[__builtin_popcount(s[i])][s[i]]++;
        B[s[i]]++;
    }
    fib[1]=1;
    for(int i=2;i<1<<17;i++)fib[i]=(fib[i-1]+fib[i-2])%mod;
    FWT::n=1<<17;
    for(int i=0;i<17;i++)FWT::fwt_or(A[i]);
    for(int x=0;x<18;x++){
        for(int i=0;i<=x;i++){
            for(int j=0;j<FWT::n;j++){
                C[x][j]+=A[i][j]*A[x-i][j]%mod;
                C[x][j]%=mod;
            }
        }
        FWT::ifwt_or(C[x]);
    }
    FWT::fwt_xor(B);
    for(int i=0;i<1<<17;i++)D[i]=B[i]*B[i]%mod;
    FWT::ifwt_xor(D);
    FWT::ifwt_xor(B);
    vector<int> E(1<<17);
    for(int i=0;i<1<<17;i++)E[i]=C[__builtin_popcount(i)][i];
    for(int i=0;i<1<<17;i++){
        E[i]=E[i]*fib[i]%mod;
        D[i]=D[i]*fib[i]%mod;
        B[i]=B[i]*fib[i]%mod;
    }
    FWT::fwt_and(E);
    FWT::fwt_and(D);
    FWT::fwt_and(B);
    for(int i=0;i<1<<17;i++)E[i]=E[i]*D[i]%mod*B[i]%mod;
    FWT::ifwt_and(E);
    int ans=0;
    for(int i=0;i<=17;i++){
        ans=(ans+E[1<<i])%mod;
    }
    cout<<ans<<"\n";
}

P4221 [WC2018] 州区划分 ​

小 S 现在拥有 nn 座城市，第 ii 座城市的人口为 wiw_i，城市与城市之间可能有双向道路相连。

现在小 S 要将这 nn 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。

假设小 S 将这些城市划分成了 kk 个州，设 ViV_i 是第 ii 个州包含的所有城市组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 00），则称这个州是不合法的。

定义第 ii 个州的满意度为：第 ii 个州的人口在前 ii 个州的人口中所占比例的 pp 次幂，即：

(∑x∈Viwx∑j=1i∑x∈Vjwx)p\left(\dfrac{\sum _ {x \in V _ i} w _ x}{\sum _ {j = 1} ^ i \sum _ {x \in V _ j} w _ x}\right) ^ p

定义一个划分的满意度为所有州的满意度的乘积。

求所有合法的划分方案的满意度之和。

答案对 998244353998244353 取模。 两个划分 {V1,V2,⋯ ,Vk}\{V_1, V _ 2, \cdots, V_k\} 和 {C1,C2,⋯ ,Cs}\{C_1, C _ 2, \cdots, C_s\} 是不同的，当且仅当 k≠sk \neq s，或存在某个 1≤i≤k1 \leq i \leq k，使得 Vi≠CiV_i \neq C_i。

xp−1≡1(modp)x^{p-1} \equiv 1 \pmod p，其中 pp 为质数， x∈[1,p)x \in [1,p)。

保证对于所有数据有：0≤n≤210 \leq n \leq 21， 0≤m≤n×(n−1)20 \leq m \leq \dfrac{n\times (n-1)}{2} ， 0≤p≤20 \leq p \leq 2， 1≤wi≤1001 \leq w_i \leq 100。

思路：

  • 状压枚举集合，那么该集合合法等价于不存在欧拉回路，集合的总和为WSW_S
  • 那么有dp方程dpS+=dpS⊕T∗WTpdp_S+=dp_{S \oplus T}*W_T^p,TT为子集，然后再更新dpS=dpSWSpdp_S=\frac{dp_S}{W_S^p}
  • 复杂度O(3n)O(3^n)
  • 上述做法会超时，进一步发现，dpS=∑dpT1⋅dpT2,T1∣T2=S，T1&T2=0dp_S=\sum dp_{T_1} \cdot dp_{T2},T_1|T_2=S，T_1 \& T_2=0，这是个子集卷积的形式，并且是自己卷自己
cpp
void solve(){
    int n,m,p;
    cin>>n>>m>>p;
    vector<array<int,2>> e(m);
    for(auto &[u,v]:e){
        cin>>u>>v;
        u--,v--;
    }
    vector<int> w(n),W(1<<n);
    for(int i=0;i<n;i++)cin>>w[i];
    vector<int> have(n),din(n);
    vector<int> state;
    for(int i=0;i<1<<n;i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if(i>>j&1)have[j]=1,(W[i]+=w[j])%=mod,cnt++;
            else have[j]=0;
            din[j]=0;
        }
        dsu.init(n+1);
        for(auto &[u,v]:e){
            if(have[u]&&have[v]){
                din[u]++,din[v]++;
                if(dsu.merge(u,v))cnt--;
            }
        }
        bool ok=false;
        if(cnt!=1)ok=true;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                if(din[j]%2){
                    ok=true;
                    break;
                }
            }
        }
        if(ok)state.push_back(i);
    }
    FWT::n=1<<n;
    vector A(n+1,vector<int>(1<<n)),B(n+1,vector<int>(1<<n));
    A[0][0]=1;
    for(auto mask:state)B[__builtin_popcount(mask)][mask]=qpow(W[mask],p);
    for(int i=0;i<=n;i++){
        FWT::fwt_or(B[i]);
        FWT::fwt_or(A[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            for(int k=0;k<1<<n;k++)A[i][k]+=A[j][k]*B[i-j][k]%mod,A[i][k]%=mod;
        }
        FWT::ifwt_or(A[i]);
        for(int j=0;j<1<<n;j++){
            int k=__builtin_popcount(j);
            if(i==k)A[i][j]=A[i][j]*qpow(qpow(W[j],mod-2),p)%mod;
            else A[i][j]=0;
        }
        if(i!=n)FWT::fwt_or(A[i]);
        
    }
    cout<<A[n][(1<<n)-1]<<"\n";
}

P6570 [NOI Online #3 提高组] 优秀子序列 ​

题目描述 ​

给定一个长度为 nn 的非负整数序列 A={a1,a2,⋯ ,an}A=\{a_1,a_2,\cdots,a_n\}，对于 AA 的一个子序列 B={ab1,ab2,⋯ ,abm}B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}（0≤m≤n0\le m\le n，1≤b1<b2<⋯<bm≤n1\le b_1<b_2<\cdots<b_m\le n，下同），称 BB 是 AA 的优秀子序列当且仅当，其任意两个不同元素的按位与结果均为 00，即：∀1≤i<j≤m\forall 1\le i<j\le m，满足：abi and abj=0a_{b_i}~\mathrm{and}~a_{b_j}=0，其中  and ~\mathrm{and}~ 是按位与运算。

对于子序列 B={ab1,ab2,⋯ ,abm}B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}，我们定义其价值为 φ(1+∑i=1mabi)\varphi(1+\sum_{i=1}^m a_{b_i})，其中 φ(x)\varphi(x) 表示小等于 xx 的正整数中与 xx 互质的数的个数。

现在请你求出 AA 的所有优秀子序列的价值之和，答案对 109+710^9+7 取模。

数据规模与约定 ​

  • 对于 10%10\% 的数据，保证 ai≤1a_i\le 1。
  • 对于 30%30\% 的数据，保证 ai≤1000a_i\le 1000。
  • 对于 60%60\% 的数据，保证 ai≤30000a_i\le 30000。
  • 另有 10%10\% 的数据，保证 n≤20n\le 20。
  • 对于 100%100\% 的数据，保证 1≤n≤1061\le n\le 10^6，0≤ai≤2×1050\le a_i\le 2\times 10^5。

思路：

  • 就是求多个数的子集卷积，但是是没有顺序的，也就是要去重
cpp
void solve(){
    int n;
    cin>>n;
    int m=FWT::init(2e5);
    sieve(1<<m);
    vector<int> A(1<<m);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        A[x]++;
    }
    vector B(m+1,vector<int>(1<<m)),C(m+1,vector<int>(1<<m));
    for(int i=1;i<1<<m;i++)B[__builtin_popcount(i)][i]=A[i];
    for(int i=0;i<=m;i++){
        FWT::fwt_or(B[i]);
        for(int j=0;j<1<<m;j++)B[i][j]=B[i][j]*i%mod;
    }
    for(int i=0;i<1<<m;i++){
        C[0][i]=1;
        for(int j=1;j<=m;j++){
            int sum=0;
            for(int k=1;k<=j;k++)sum=(sum+B[k][i]*C[j-k][i]%mod)%mod;
            C[j][i]=sum*qpow(j,mod-2)%mod;
        }
    }
    for(int i=0;i<=m;i++)FWT::ifwt_or(C[i]);
    int ans=1;
    for(int i=0;i<1<<m;i++){
        ans=(ans+phi[1+i]*C[__builtin_popcount(i)][i]%mod)%mod;
    }
    cout<<ans*qpow(2,A[0])%mod<<"\n";
}

CF662C Binary Table ​

题目描述 ​

有一个 nn 行 mm 列的表格，每个元素都是 0/10/1 ，每次操作可以选择一行或一列，把 0/10/1 翻转，即把 00 换为 11 ，把 11 换为 00 。请问经过若干次操作后，表格中最少有多少个 11 。

输入格式 ​

第一行是两个整数 nn 和 mm （ 1⩽n⩽20,1⩽m⩽1051\leqslant n\leqslant 20,1\leqslant m\leqslant 10^5 ）之后 nn 行，每行 mm 个数字 0/10/1 ，注意数字间无空格。

思路：

  • 我们枚举要翻转的行的状态为ii，那么每一列的状态原来为jj，变为i⊕ji \oplus j，那么该列的个数即为0和10和1的最小值
  • 假设aia_i表示状态为ii的个数，那么答案为min⁡(aj⋅bi⊕j)\min(a_j \cdot b_{i \oplus j})即min⁡j⊕k=iaj⋅bk\min_{j \oplus k =i}a_j \cdot b_k
  • 上fwt板子
cpp
char a[25][100010];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    FWT::n=1<<n;
    vector<int> A(1<<n),B(1<<n);
    for(int j=1;j<=m;j++){
        int s=0;
        for(int i=1;i<=n;i++){
            s+=(a[i][j]-'0')<<i-1;
        }
        A[s]++;
    }
    for(int i=0;i<1<<n;i++){
        int a=0,b=0;
        for(int j=0;j<n;j++){
            if(i>>j&1)a++;
            else b++;
        }
        B[i]=min(a,b);
    }
    FWT::fwt_xor(A);
    FWT::fwt_xor(B);
    for(int i=0;i<1<<n;i++)A[i]=A[i]*B[i]%mod;
    FWT::ifwt_xor(A);
    int ans=INF;
    for(int i=0;i<1<<n;i++)ans=min(ans,A[i]);
    cout<<ans<<"\n";
}

AT_abc212_h [ABC212H] Nim Counting ​

题目描述 ​

给定两个数 N,KN,K，以及一个长度为 KK 的整数数组 (A1,A2,⋯ ,AK)(A_1,A_2,\cdots, A_K)。

两个人玩 Nim 游戏。

现在通过以下方式生成一个游戏：

任意选择一个 1≤M≤N1\le M\le N，MM 表示石子堆数。

对于每一堆，其石子数是 AA 中任意一个数。

对于 ∑i=1NKi\sum_{i=1}^N K^i 种游戏，求先手获胜的游戏数，答案对 998244353998244353 取模。

思路：

  • 定义fi,jf_{i,j}表示有ii堆石子，异或和为jj的方案数
  • fi,j=∑=k⊕x=jfi,k⋅f1,xf_{i,j}=\sum={k \oplus x=j} f_{i,k} \cdot f_{1,x}
  • FWT(i)=FWT(i−1)∗FWT(1)FWT(i)=FWT(i-1) *FWT(1)
  • FWT(i)=FWT(1)iFWT(i)=FWT(1)^i
  • 正变换后求等比数列，再逆回去即可
cpp
void solve(){
    int n,K;
    cin>>n>>K;
    FWT::n=1<<16;
    vector<int> f(FWT::n);
    for(int i=0;i<K;i++){
        int x;
        cin>>x;
        f[x]++;
    }
    FWT::fwt_xor(f);
    for(int i=0;i<FWT::n;i++){
        if(f[i]==1)f[i]=n;
        else f[i]=f[i]*(qpow(f[i],n)-1)%mod*qpow(f[i]-1,mod-2)%mod;
    }
    FWT::ifwt_xor(f);
    int ans=0;
    for(int i=1;i<FWT::n;i++)ans=(ans+f[i])%mod;
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025