题解：P16500 【MX-S14-T3】「KWOI R2」XOR and Sum of Subsets

· · 题解

前言

提供一种不需要科技的做法，感谢大佬 @Miss_SGT 提供讲解。

思路

首先求出 S 的线性基 T，设线性基的大小为 c，那么答案即为线性基能组成的数对应的 a 之和乘上 2^{|S|-c}。暴力枚举每个基底选不选即可做到单次询问 O(2^c)。

当 c 很大时，上述算法显然会超时。但如果有一个 O(2^{n-c}) 的做法，平衡一下刚刚好。

令 x^ax^b=x^{a\oplus b}，容易发现，答案可以化作下面的形式：

\sum_{i=0}^{2^n-1} a_i\left([x^i]\prod\limits_{j\in T}(1+x^j)\right)

考虑后面多项式的 FWT，如下：

\operatorname{FWT}\left(\prod\limits_{i\in T}(1+x^i)\right)[j]=\prod_{i\in T}\left(1+(-1)^{\operatorname{popcount}(i\operatorname{and} j)\bmod 2}\right)

也就是说，FWT 后的第 j 项不为零，当且仅当对于每个 i\in T，\operatorname{popcount}(i\operatorname{and}j) 都是偶数。且当此项不为零的时候，其值一定是 2^c。

我们先对 T 做一遍高斯消元，使得在线性基内的每一个位互相独立，即我让某个基内元素选，不会影响其他基内元素最高位对应的值。

此时有一个很好的性质，若确定基内元素最高位之外的位选不选，基内元素的选择就是唯一的了。所以说，FWT 之后有值的项就只有 O(2^{n-c}) 个。

所以我们要把答案化为和 FWT 数组有关的形式，这是经典的，具体如下：

\begin{aligned} ans &=\sum_{i=0}^{2^n-1} a_i\left([x^i]\prod\limits_{u\in T}(1+x^u)\right)\\ &=\sum_{i=0}^{2^n-1} a_i\times \operatorname{IFWT}\left(\operatorname{FWT}\left(\prod\limits_{u\in T}(1+x^u)\right)\right)[i]\\ &=\sum_{i=0}^{2^n-1} a_i\times \sum_{j=0}^{2^n-1}\frac{1}{2^{n}}(-1)^{\operatorname{popcount}(i\operatorname{and} j)\bmod 2}\operatorname{FWT}\left(\prod\limits_{u\in T}(1+x^u)\right)[j]\\ &=\sum_{j=0}^{2^n-1} \operatorname{FWT}\left(\prod\limits_{u\in T}(1+x^u)\right)[j] \sum_{i=0}^{2^n-1}\frac{1}{2^n}(-1)^{\operatorname{popcount}(i\operatorname{and} j)\bmod 2} a_i\\ &=\sum_{i=0}^{2^n-1} \operatorname{FWT}\left(\prod\limits_{u\in T}(1+x^u)\right)[i]\times \operatorname{IFWT}\left(a\right)[i] \end{aligned}

所以我们只需要预处理出 \operatorname{IFWT}(a)，然后暴力枚举每个除开基内元素最高位的位选不选，从而得到 \operatorname{FWT}\left(\prod\limits_{u\in T}(1+x^u)\right) 不为零的项，计算答案即可。精细实现即可做到 O(2^{n-c}+n^2)。

所以总复杂度为 O(q2^{\frac{n}2}+qn^2)，可以通过。实现方式可以参考代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 25,mod = 998244353;
inline int qpow(int x,int y)
{
    y = (y+mod-1)%(mod-1);
    int res = 1;
    while(y)
    {
        if(y&1) res = 1ll*res*x%mod;
        y>>=1;
        x = 1ll*x*x%mod;
    }
    return res;
}
int n,q,a[1<<20],f[1<<20];
int h[N],tmp[N],cnt,g[1<<20];
inline void ins(int x)
{
    for(int i = n-1;~i;i--)
        if((x>>i)&1)
        {
            if(!h[i]) return h[i] = x,void();
            x^=h[i];
        }
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i = 0;i<(1<<n);i++)
        cin>>a[i],f[i] = a[i];
    for(int k = 1;k<(1<<n);k<<=1)
        for(int i = 0;i<(1<<n);i+=k*2)
            for(int j = 0;j<k;j++)
            {
                int x = f[i+j],y = f[i+j+k];
                f[i+j] = (x+y)%mod,f[i+j+k] = (x+mod-y)%mod;
            }
    while(q--)
    {
        for(int i = 0;i<n;i++) h[i] = 0;
        int len;cin>>len;
        for(int i = 1,x;i<=len;i++)
            cin>>x,ins(x);
        cnt = 0;
        for(int i = 0;i<n;i++)
            if(h[i]) tmp[cnt++] = i;
        if(cnt<=n/2)
        {
            long long ans = 0;
            for(int i = 0;i<cnt;i++)
                g[1<<i] = h[tmp[i]];
            for(int z = 0;z<(1<<cnt);z++)
            {
                if(z) g[z] = g[z-(z&(-z))]^g[z&(-z)];
                ans+=a[g[z]];
            }
            cout<<ans%mod*qpow(2,len-cnt)%mod<<'\n'; 
        }
        else
        {
            for(int i = cnt-1;i;i--)
                for(int j = i-1;~j;j--)
                    if((h[tmp[i]]>>tmp[j])&1) h[tmp[i]]^=h[tmp[j]];
            int cnt2 = 0;
            for(int i = 0;i<n;i++)
                if(!h[i])
                {
                    int now = (1<<i);
                    for(int j = 0;j<cnt;j++)
                        if((h[tmp[j]]>>i)&1) now|=(1<<tmp[j]);
                    g[1<<cnt2] = now;
                    cnt2++;
                }
            long long ans = 0;
            for(int z = 0;z<(1<<cnt2);z++)
            {
                if(z) g[z] = g[z-(z&(-z))]^g[z&(-z)];
                ans+=f[g[z]];
            }
            cout<<ans%mod*qpow(2,len-n)%mod<<'\n';
        }
    }
    return 0;
}