QOJ 6344 The Best Problem of 2021

· · 个人记录

题目描述

给定 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。

由题意得，$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} 表示：

初始值 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;
}