CF1336E Chiori and Doll Picking 题解

绝顶我为峰 · 2023-03-22 15:27:26 · 题解

思路来自 ix35，orzorzorz。

好题，好题啊。

题意翻译说的很清楚了，直接说做法。

记 |S|=\mathrm{popcount(S)}，\mathrm{span}(A) 为基底 A 张成的线性空间，|\mathrm{span}(A)| 表示 A 张成的线性空间的大小，(i,j)=|i \land j|\mod 2，也即向量 i 与向量 j 的内积。

显然我们应该建出这个序列的线性基 A，我们记这个线性基的秩为 r(A)。

则答案是 ans_i=2^{n-r(A)}\sum\limits_{x\in\mathrm{span}(A)}[|x|=i]，直接枚举 \mathrm{span}(A) 中的每一个向量即可做到 O(2^{r(A)})。

这个做法适用于 r(A) 小的情况，对于 r(A) 较大的情况，考虑求出 A 的正交线性基 B，我们有结论 [x\in \mathrm{span}(A)]=\frac1{|\mathrm{span}(B)|}\sum\limits_{y\in\mathrm{span}(B)}(-1)^{(x,y)}。

为了证明这个结论我们先证明引理： [z^T]\mathrm{FWT}(F(\mathrm{span}(A))) 只有 0,2^{r(A)} 两种取值。其中 F(z)=\sum\limits_Tf_Tz^T，是一个集合幂级数。

引理证明：考虑线性空间任意异或一个数后线性空间不变，因此有 F(\mathrm{span}(A))\times z^P=F(\mathrm{span}(A))。

把线性空间中所有向量代入上式求和可以得到 F(\mathrm{span}(A))\times F(\mathrm{span}(A))=2^{r(A)}\times F(\mathrm{span}(A))。

两边同时 \mathrm{FWT}，可以得到 \mathrm{FWT}(F(\mathrm{span}(A)))\cdot\mathrm{FWT}(F(\mathrm{span}(A)))=2^{r(A)}\times\mathrm{FWT}(F(\mathrm{span}(A)))。

因此对于任意系数都有 z^2=2^{r(A)}z 这个方程显然只有 z=0,z=2^{r(A)} 两个解，因此引理得证。

这个引理有一个显然的推论：[z^T]\mathrm{FWT}(F(\mathrm{span}(A))) 取 2^{r(A)} 当且仅当 \forall S\in \mathrm{span}(A),(S,T)=0，也即 T 和 \mathrm{span}(A) 中所有向量正交，我们称这为 T 与 \mathrm{span}(A) 正交。

再来考虑我们要证明的结论，发现 \sum\limits_{y\in\mathrm{span}(B)}(-1)^{(x,y)}=[z^x]\mathrm{FWT}(F(\mathrm{span}(B))，根据正交线性基的定义，一个向量 P 与 \mathrm{span}(B) 正交当且仅当 P\in \mathrm{span}(A)，因此结论得证。

证明了这个结论我们再回来看我们要求的答案，可以得到 ans_i=2^{n-r(A)}\sum\limits_{x\in\mathrm{span}(A)}[|x|=i]=2^{n-r(A)}\sum\limits_{|x|=i}[x\in\mathrm{span}(A)]=\frac{2^{n-r(A)}}{|\mathrm{span}(B)|}\sum\limits_{|x|=i}\sum\limits_{y\in\mathrm{span}(B)}(-1)^{(x,y)}=2^{n-r(A)-r(B)}\sum\limits_{y\in\mathrm{span}(B)}\sum\limits_{|x|=i}(-1)^{(x,y)}

发现向量的每一位是本质相同的，因此 \sum\limits_{|x|=i}(-1)^{(x,y)} 的值只和 |x|,|y| 有关，我们记为 f(|x|,|y|)，则容易得到 f(|x|,|y|)=\sum\limits_{i=0}^m(-1)^i\dbinom {|y|}i\dbinom{m-|y|}{|x|-i}，容易在 O(m^3) 的时间内预处理出全部 f 的值。

那么我们要求的答案就是 ans_i=2^{n-m}\sum\limits_{j=0}^mf(i,j)\sum\limits_{y\in\mathrm{span}(B)}[|y|=j]，其中 \sum\limits_{y\in\mathrm{span}(B)}[|y|=j] 直接枚举 \mathrm{span}(B) 中的所有元素容易在 O(2^{r(B)})=O(2^{m-r(A)}) 的复杂度内得到，于是我们有了一个 O(2^{m-r(A)}) 的做法。

最后我们将两个做法合并，r(A)\leq \frac m2 时使用 O(2^{r(A)}) 的做法，否则使用 O(2^{m-r(A)}) 的做法，如果我们可以以低于 O(2^{m-r(A)}) 的复杂度构造出 A 的正交线性基 B，就可以在 O(2^{\frac m2}) 的时间复杂度内通过本题。

正交线性基的一个构造方法是先对线性基高消使得主元所在的列只有一个 1，然后将非主元列转置即可，下图是一个构造的例子，其中 A 是原线性基，B 是构造出的正交线性基（直接拉了别人的图）：

于是可以在 O(m^2) 的时间复杂度内构造 A 的正交线性基 B，因此我们在 O(2^{\frac m2}) 的时间复杂度内解决了本题。

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int mod=998244353;
int n,m,a[55],w[200001],cnt,b[55],c[55][55],sum[55][55],p[200001],ans[55],res[55];
inline void init()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
}
inline int read()
{
    int x;
    cin>>x;
    return x;
}
inline int pw(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=1ll*res*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return res;
}
inline int Mod(int x)
{
    return x>=mod? x-mod:x;
}
inline void ins(int x)
{
    for(int i=m-1;~i;--i)
        if(x>>i&1)
        {
            if(!a[i])
            {
                a[i]=x;
                ++cnt;
                return;
            }
            x^=a[i];
        }
}
inline void T()
{
    for(int i=m-1;~i;--i)
        for(int j=i-1;~j;--j)
            if(a[i]>>j&1)
                a[i]^=a[j];
    for(int i=m-1;~i;--i)
        if(!a[i])
        {
            b[i]=1ll<<i;
            for(int j=m-1;~j;--j)
                b[i]|=(a[j]>>i&1)<<j;
        }
    for(int i=0;i<m;++i)
        a[i]=b[i];
}
inline void dfs1(int k,int val)
{
    if(k>cnt)
    {
        int t=__builtin_popcountll(val);
        ans[t]=Mod(ans[t]+p[n-cnt]);
        return;
    }
    dfs1(k+1,val);
    dfs1(k+1,val^b[k]);
}
inline void dfs2(int k,int val)
{
    if(k>cnt)
    {
        int t=__builtin_popcountll(val);
        ++res[t];
        return;
    }
    dfs2(k+1,val);
    dfs2(k+1,val^b[k]);
}
signed main()
{
    init();
    n=read(),m=read();
    p[0]=1;
    for(int i=1;i<=n;++i)
        p[i]=Mod(p[i-1]<<1);
    if(!m)
    {
        cout<<p[n]<<'\n';
        cout.flush();
        return 0;
    }
    for(int i=1;i<=n;++i)
        ins(w[i]=read());
    if(cnt<=(m>>1))
    {
        int tmp=0;
        for(int i=0;i<m;++i)
            if(a[i])
                b[++tmp]=a[i];
        dfs1(1,0);
    }
    else
    {
        T();
        cnt=m-cnt;
        c[0][0]=1;
        for(int i=1;i<=m;++i)
        {
            c[i][0]=1;
            for(int j=1;j<=i;++j)
                c[i][j]=Mod(c[i-1][j]+c[i-1][j-1]);
        }
        for(int i=0;i<=m;++i)
            for(int j=0;j<=m;++j)
                for(int k=0;k<=m;++k)
                    if(k<=i&&j-k<=m-i&&j-k>=0)
                        sum[i][j]=Mod(sum[i][j]+1ll*(k&1? mod-1:1)*c[i][k]%mod*c[m-i][j-k]%mod);
        int tmp=0;
        for(int i=0;i<m;++i)
            if(a[i])
                b[++tmp]=a[i];
        dfs2(1,0);
        int inv=pw(p[cnt],mod-2);
        for(int i=0;i<=m;++i)
        {
            for(int j=0;j<=m;++j)
                ans[i]=Mod(ans[i]+1ll*res[j]*sum[j][i]%mod);
            ans[i]=1ll*ans[i]*inv%mod*p[n-(m-cnt)]%mod;
        }
    }
    for(int i=0;i<=m;++i)
        cout<<ans[i]<<" ";
    cout<<'\n';
    cout.flush();
    return 0;
}