题目描述

给定 $n$ 个 $m$ 位二进制非负整数 $B_1,B_2,\cdots B_n$ 和一个 $m$ 位二进制整数 $X$，求 $\left\{1,2,\cdots X\right\}$ 有多少个子集 $S$ 满足 $B$ 是 $S$ 的一组基。且 $S$ 的秩为 $n$。答案对 $998244353$ 取模。

$n,m\le 2000$

题解

以下第 $i$ 位均从第 $0$ 位开始。

定义 $\mathrm{Hi}\left(x\right)$ 为 $x$ 的最高位。

首先将 $B_1,B_2,\cdots B_n$ 依次插入线性基消元，使得 $\mathrm{Hi}\left(B_1\right)> \mathrm{Hi}\left(B_2\right)\cdots >\mathrm{Hi}\left(B_n\right)$，且对于任意的 $j\neq i$，$B_j$ 第 $\mathrm{Hi}\left(B_i\right)$ 位均为 $0$，即主元列只有一个 $1$。

对于一个 $n$ 位二进制整数 $y=\left(y_{n-1}y_{n-2}\cdots y_0\right)$，其中 $y_{n-1}$ 为最高位，$y_0$ 为最低位，定义:

$$ f\left(y\right)=\bigoplus_{y_{i}=1}B_{n-i} $$

由于主元列只有一个 $1$，因此 $f\left(y\right)$ 是单调的，存在一个 $Y$，使得 $f\left(y\right)\le X$ 的充要条件是 $y\le Y$。

$\mathcal{O}\left(\dfrac{n^3}{w}+n^2\right)$ 预处理即可求出这个 $Y$。

由题意得，$S\subseteq\left\{f\left(y\right)\right\}$，于是问题转化为，对于一个 $Y$，求出 $\mathcal{M}=\left\{1,2,\dots Y\right\}$ 有多少个子集满足其秩为 $n$。

考虑对于每个 $d$，求出，对于 $V=\left\{0,1,2,\dots,2^n-1\right\}$ 的每个维数为 $d$ 的子空间 $V_0$，$V_0\cap \mathcal{M}$ 的子集数之和，设其为 $c_d$

那么，设 $\mathcal M$ 的秩为 $k$ 的子集个数为 $t_k$，则

$$ c_k=\sum_{i}\left[\begin{matrix}n-i\\k-i\end{matrix}\right]_2\times t_i $$

其中 $\left[\begin{matrix}n-i\\k-i\end{matrix}\right]_2$ 为 q-binomial。

那么，求出 $c_i$ 后，可以 $\mathcal{O}\left(n^2\right)$ 递推得到 $t_n$。

因为，对于 $V$ 的子空间 $V_0$，$V_0$ 恰有一组基 $a_1,a_2,\cdots a_l$ 满足 $\mathrm{Hi}\left(a_1\right)> \mathrm{Hi}\left(a_2\right)>\cdots \mathrm{Hi}\left(a_l\right)$。对于任意的 $j\neq i$，$a_j$ 第 $\mathrm{Hi}\left(a_i\right)$ 位均为 $0$，即主元列只有一个 $1$。

同理，这里只需找到 $L$，满足 $\le L$ 的每个 2 进制整数对应的数都 $\le Y$

从 $Y$ 低位往高位 dp，设 $f_{i,j}$ 表示：

• 当前已经确定了 $a_{l-j+1},a_{l-j+2},\dots a_l$，$a_1,a_2,\dots a_{l-j}$ 都还未确定。$\mathrm{Hi}\left(a_1\right)>\mathrm{Hi}\left(a_2\right)\cdots >\mathrm{Hi}\left(a_{l-j}\right)\ge i> \mathrm{Hi}\left(a_{l-j+1}\right)>\cdots >\mathrm{Hi}\left(a_l\right)$
• $\left\{a_1,a_2,\cdots a_{l-j}\right\}$ 存在一个子集满足其异或和为 $T$，$T$ 和 $Y$ 的高 $n-i$ 位都相同，由此可知 $T$ 是唯一的。
• 对于所有满足以上两个条件的 $\left\{a_{l-j+1},a_{l-j+2},\cdots a_l\right\}$，以及 $a_{1},a_{2},\cdots a_{l-j}$ 的后 $i$ 位，令 $\displaystyle\left\{T\bigoplus_{i\in S}a_{i}\mid \forall S\subseteq \left(l-j,l\right]\cap Z\right\}\bigcap \left\{\le Y\right\}=t$，$2^t$ 之和。

初始值 $f_{0,0}=2$

考虑 $f_{i,j}$ 转移：

令 $c$ 为 $y_{i-1}$，即 $\left(Y>>{i-1}\right)\&1$。

第一种情况：第 $i-1$ 位有一个基，则 $T$ 的第 $i-1$ 位也为 $0$

(1) $c=0$，则匹配时 $i-1$ 位必须不选，即 $L$ 的 $a_{j}$ 对应的那一位为 $0$

$$ f_{i,j}\leftarrow f_{i-1,j-1} $$

(2) $c=1$，则匹配时 $i$ 位要选，即 $L$ 的 $a_{j}$ 对应的那一位为 $1$，此时 $\displaystyle\left\{T\bigoplus_{i\in S}a_{i}\mid \forall S\subseteq \left(l-j,l\right]\cap Z\right\}\bigcap \left\{\le Y\right\}$ 多出了 $\displaystyle 2^{j-1}$ 个数，因此转移式为：

$$ f_{i,j}\leftarrow f_{i-1,j-1}\times 2^{2^{j-1}} $$

第二种情况：第 $i-1$ 位没有基，以下分类讨论 $T$ 的第 $i-1$ 位 $v=t_{i-1}$ 和 $c$ 的取值。

对于每种 $v$ 可能的取值，都有 $2^{l-j-1}$ 种方式使得 $T$ 的这一位为 $0$

(1) $c=v=0$

$$ f_{i,j}\leftarrow f_{i-1,j}\times 2^{l-j-1} $$

(2) $c=v=1$

$$ f_{i,j}\leftarrow f_{i-1,j}\times 2^{l-j-1} $$

(3) $1=c>v=0$ 此时后面 $j$ 个基可以任选， $a_{1},a_2,\cdots a_{l-j}$ 的低 $i-1$ 位中，除去那些主元列，剩下 $i-1-j$ 个位置都可以任选。每种贡献 $2^{2^j}$

$$ f_{i,j}\leftarrow 2^{2^{j}}\times 2^{\left(l-j\right)\times \left(i-j\right)-1}\times \left[\begin{matrix}i-1\\j\end{matrix}\right]_2 $$

(4) $0=c<v=1$ 此时和上面那种情况类似，但贡献变为 $1$。

$$ f_{i,j}\leftarrow 1\times 2^{\left(l-j\right)\times \left(i-j\right)-1}\times \left[\begin{matrix}i-1\\j\end{matrix}\right]_2 $$

需要额外分类讨论一下 $\mathrm{Hi}\left(a_1\right)$ 是否为 $n$。因为当 $j=l$ 时，$T$ 的每一位必定是 $0$。

由于 $dp$ 时不知道 $l$ 的值，而 $f_{i,j}$ 中恰好有 $i-j$ 个 $2^{l}$，因此可以把 $2^l$ 提取出来最后再乘。

知道 $f_{i,j}$ 就可以计算出 $c_k$ 了。算答案时要除以 $2$，因为不需要考虑 $0$ 这个数。

总复杂度 $\mathcal{O}\left(\dfrac{n^3}{w}+n^2\right)$

Code

#include <iostream>
#include <algorithm>
#include <bitset>
constexpr int N(2010),p(998244353);
std::bitset<N> b[N];bool hv[N];
int fp(int a,int b){int ans(1),off(a);while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n,m;
    std::cin>>n>>m;
    static std::bitset<N> a[N],xb;
    for(int i(1);i<=n;++i)
    {
        static char s[N];std::cin>>s;
        for(int j(0);j<m;++j)
        {
            a[i][m-j-1]=(s[j]=='1');
        }
        bool st(false);
        for(int j(m-1);j>=0;--j) if(a[i][j])
        {
            if(hv[j])
            {
                a[i]^=b[j];
            }
            else
            {
                hv[j]=st=true;
                b[j]=a[i];
                break;
            }
        }
        if(!st){std::cout<<0<<std::endl;return 0;}
    }
    {
        static char s[N];std::cin>>s;
        for(int j(0);j<m;++j) xb[m-j-1]=(s[j]=='1');
    }
    for(int i(m-1);i>=0;--i) if(hv[i]) for(int j(i+1);j<m;++j) if(hv[j] && b[j][i]) b[j]^=b[i];
    static int x[N];int cnt(0);
    static std::bitset<N> cur;
    for(int j(m-1);j>=0;--j) if(hv[j])
    {
        std::bitset<N> nw(cur^b[j]);
        bool cap(true);
        for(int t(m-1);t>=0;--t) if(xb[t]!=nw[t])
        {
            if(xb[t]<nw[t]) cap=false;
            break;
        }
        if(cap) cur=nw,x[++cnt]=1;
        else x[++cnt]=0;
    }
    if(!x[1]){std::cout<<0<<std::endl;return 0;}
    static int p2[N],pp2[N],ip2[N],ipr[N][N],inv[N];p2[0]=1;pp2[0]=2;ip2[0]=1;
    constexpr int inv2((p+1)/2);
    static int f[N][N],g[N][N];
    for(int i(1);i<N;++i) p2[i]=2ll*p2[i-1]%p,pp2[i]=1ll*pp2[i-1]*pp2[i-1]%p,ip2[i]=1ll*ip2[i-1]*inv2%p;
    inv[1]=1;for(int i(2);i<N;++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    for(int i(0);i<=n;++i){ipr[i][0]=1;for(int j(1);j<=n;++j) ipr[i][j]=1ll*ipr[i][j-1]*ip2[i]%p;}
    static int qf[N],iqf[N];
    qf[0]=iqf[0]=1;for(int i(1);i<N;++i) qf[i]=1ll*qf[i-1]*(p2[i]-1)%p,iqf[i]=fp(qf[i],p-2);
    auto qb=[](int a,int b)->int{return 1ll*qf[a]*iqf[b]%p*iqf[a-b]%p;};
    f[0][0]=2;
    for(int i(1);i<n;++i)
    {
        int c(x[n-i+1]);
        for(int j(0);j<=i;++j)
        {
            unsigned long long cur(0);
            if(c==0)
            {
                cur+=1ll*ipr[i-j][j]*inv2%p*qb(i-1,j);
                cur+=1ll*ip2[j+1]*f[i-1][j];
                if(j) cur+=f[i-1][j-1];
            }
            else
            {
                cur+=1ll*pp2[j]*ipr[i-j][j]%p*inv2%p*qb(i-1,j);
                cur+=1ll*ip2[j+1]*f[i-1][j];
                if(j) cur+=1ll*f[i-1][j-1]*pp2[j-1];
            }
            f[i][j]=cur%p;
        }
    }
    static int sum[N];
    sum[0]=1;
    for(int j(1);j<=n;++j)
    {
        sum[j]=(1ll*f[n-1][j-1]*pp2[j-1]%p*fp(2,(n-j)*j)+1ll*pp2[j]*qb(n-1,j))%p*inv2%p;
    }
    for(int j(0);j<=cnt;++j)
    {
        for(int k(0);k<j;++k)
        {
            sum[j]=(sum[j]+1ll*(p-sum[k])*qb(cnt-k,j-k))%p;
        }
    }
    std::cout<<sum[n]<<std::endl;
    return 0;
}