题目描述

有一个 $n\times m$ 的网格，第 $i$ 行第 $j$ 列内可以填写一个 $[0,a_{i,j}]$ 范围内的整数。你需要求出满足以下所有条件的填写方案数：

• 网格中每个位置都填有数，且不全为 $0$；
• 对于每一行，至多有一个位置非 $0$；
• 设不全为 $0$ 的行有 $k$ 行，则对于每一列，填非 $0$ 数的位置个数不超过 $\lfloor\frac{k}{2}\rfloor$。

答案对 $998\ 244\ 353$ 取模。

$n\le 100$，$m\le 2000$。

解析

首先先忽略第三个条件，看看满足前两个条件的方案有哪些。

再忽略第一个条件中“整个网格不全为 $0$”的限制，方案数显然为

$$\prod_{i=1}^n \bigg(\sum_{j=1}^m a_{i,j}+1\bigg)$$

（最后的 $+1$ 是全 $0$ 的情况）

这时再把第一个条件补上，则上面的方案数 $-1$ 即可。

这时，考虑第三个条件。这等价于“将填了非 $0$ 数的列的编号作为可重集，则可重集中不存在绝对众数”。

“没有绝对众数”的方案无法很好地统计，于是转而统计“有绝对众数”的方案数。这就是上面为什么要求总方案数的原因（也很好求）。

首先，绝对众数若存在，则恰好有一个。所以，考虑钦定绝对众数存在于第 $j$ 列。

然后，考虑 DP。

如果设 $f_{i,x,y}$ 表示“前 $i$ 行中选了 $x$ 行填非 $0$，$y$ 行选择了第 $j$ 列的方案数”，则这即使能 $O(1)$ 转移（确实能做到），那整体时间复杂度也会是 $O(n^3m)$ 的（枚举 $j$ 是 $O(m)$ 的，状态是 $O(n^3)$ 的），无法通过。

考虑摩尔投票的技巧：我们只关心最终填了 $j$ 的行是否严格多于填了其他非 $0$ 列的行即可。所以考虑把 $x,y$ 两维压成一维 $d=y-(x-y)$，表示考虑到第 $i$ 行时填 $j$ 的行与填其他非 $0$ 列的行的个数差。

于是重新设计状态 $g_{i,d}$（$i\in [1,n]$，$d\in [-n,n]$），定义见上。易得转移方程为：

$$g_{i,d}=g_{i-1,d}+g_{i-1,d+1}\times\bigg(\sum_{j'\neq j}a_{i,j'}\bigg)+g_{i-1,d-1}\times a_{i,j}$$

三项分别为这行填全 $0$、这行填非 $j$ 列、这行填 $j$ 列的方案数。初始化 $g_{0,0}=1$，其他全为 $0$。

对于一个固定的 $j$，存在绝对众数的方案数为

$$\sum_{d=1}^n g_{n,d}$$

根据 $\sum_{j'\neq j}a_{i,j'}=\sum a_{i,j'}-a_{i,j}$，直接在输入时处理 $\sum a_{i,j'}$ 即可在 $O(n^2m)$ 的时间复杂度下通过本题。

AC Code

为防止下标为负数，需要将其加上一个大常数，同时 DP 数组开二倍空间。

#include <bits/stdc++.h>
using namespace std;
#define LL long long

#define N 105
#define M 2005
const int mod = 998244353;

namespace OPT{
    int a[N][M],s[N],g[N][N<<1];
    void main(){
        int n,m;
        cin>>n>>m;
        int All=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cin>>a[i][j],s[i]=(s[i]+a[i][j])%mod;
            All=All*1ll*((s[i]+1)%mod)%mod;
        }
        All=(All-1+mod)%mod;

        int Inc=0;
        for(int j=1;j<=m;j++){
            int res=0;
            for(int i=-n;i<=n;i++) g[0][N+i]=0;
            g[0][N]=1;
            for(int i=1;i<=n;i++)
                for(int d=-n;d<=n;d++){
                    int now1=g[i-1][N+d];
                    int now2=g[i-1][N+d+1]*1ll*((s[i]-a[i][j]+mod)%mod)%mod;
                    int now3=g[i-1][N+d-1]*1ll*a[i][j]%mod;
                    g[i][N+d]=((now1+now2)%mod+now3)%mod;
                }
            for(int i=1;i<=n;i++) res=(res+g[n][N+i])%mod;
            Inc=(Inc+res)%mod;
        }
        cout<<(All-Inc+mod)%mod<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    OPT::main();

    return 0;
}