更好的阅读体验

Statement

有 $1\sim n$ 种烹饪方法和 $1\sim m$ 种食材，使用 $i$ 方法，食材为 $j$ 的一共有 $a_{i,j}$ 道菜。

对于一种包含 $k$ 道菜的方案而言：

• $k\ge 1$
• 每道菜的烹饪方法不同
• 每种食材最多出现在 $\Big\lfloor \dfrac{k}{2}\Big\rfloor$ 道菜中

求有多少种不同的搭配方案，对 $998244353$ 取模。$1\leq n\leq 100,1\leq m\leq 2000$

Thoughts & Solution

对于方阵 $a$ ，题目要求就相当于是：

• 要取 $k\ge 1$ 个数
• 每行只能取一个
• 每列只能取不超过 $k\div 2$ 个。

考虑容斥，那么就是：每行至多取一个的方案 - 取了 0/1 个的方案 - 存在一列取了超过半数的方案（显然这样的列至多有一个）

对于每行至多取一个的总方案，来一遍 DP ，令 $g[i][j]$ 表示到第 $i$ 行，取了 $j$ 个的方案数，$sum[i]=\sum a_{i,j}$ 那么有：
$$ g[i][j]=g[i-1][j-1]\times sum[i]+g[i-1][j]（可以开滚动维护） $$
发现 取了 1 个的方案 其实可以直接在 存在一列取了超过半数的方案 里面统计掉，因为一定是超过半数的。

没有取的方案直接不加上就好了。

然后就可以暴力枚举超过半数的材料是哪个，进行DP。

设 $f[i][j][k]$ 表示前 $i$ 行，取了 $j$ 个，其中超过半数的 $x$ 取了 $k$ 个（ $\Big\lfloor \dfrac{j}{2}\Big\rfloor <k$），枚举到 $pos$ 这道菜取了超过半数。

转移挺好想的，就是三种情况：

• 不取
• 取了除 $pos$ 外的任意一个
• 取了 $pos$

转移方程：
$$ f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]\times (sum[i]-a[i][pos])+f[i-1][j-1][k-1]\times a[i][pos] $$
对于每个 $pos$ ，对答案的贡献就是 $\sum_{i=0}^n\sum_{j=\lfloor i/2\rfloor+1}^i f[k][i][j]$ .

这样的复杂度是 $\mathcal{O}(n^3m)$ 的，能得到 84 分的好成绩（ 在考场上已经相当可观了……

然后考虑优化。发现合法状态只有 $2\times k>j$ 的部分，也就是说你完全不需要知道 $j,k$ 的具体值，所以可以把状态搞成 $2k-j$ ，省掉一维的枚举时间和空间。

那么方程就是：
$$ f[i][j(2k-j)]=f[i-1][j]+f[i-1][j+1(2k-j+1)]\times (sum[i]-a[i][pos])+f[i-1][j-1(2k-j-1)]\times a[i][pos] $$
（数组下标内的小括号表示根据原先的 $j,k$ 定义，这个下标的值）

（注意，这里的合法状态指的是最终对答案有贡献的部分，从转移方程易知 $2k\leq j$ 的部分还是有用的，可以通过若干次 $j-1$ 部分的转移贡献到合法状态里面去）

复杂度是 $\mathcal{O}(n^2m)$ .

实现的时候注意减法取模……因为这个挂成 88 了qaq

//Author: RingweEH
const int N=110,M=2010;
const ll Mod=998244353;
int n,m;
ll a[N][M],g[N],sum[N],f[N][N<<1];

void add( ll &t1,ll t2 )
{
    t1=(t1+t2);
    if ( t1>Mod ) t1-=Mod;
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=n; i++ )
        for ( int j=1; j<=m; j++ )
            a[i][j]=read(),add( sum[i],a[i][j] );

    memset( g,0,sizeof(g) ); g[0]=1;
    for ( int i=1; i<=n; i++ )
        for ( int j=i; j>=1; j-- )
            add( g[j],g[j-1]*sum[i]%Mod );
    ll ans=0;
    for ( int i=1; i<=n; i++ )
        add( ans,g[i] );
    for ( int pos=1; pos<=m; pos++ )
    {
        memset( f,0,sizeof(f) ); f[0][n]=1;
        for ( int i=1; i<=n; i++ )
            for ( int j=1; j<=n+i; j++ )
            {
                f[i][j]=f[i-1][j];
                add( f[i][j],f[i-1][j+1]*(sum[i]+Mod-a[i][pos])%Mod );
                add( f[i][j],f[i-1][j-1]*a[i][pos]%Mod );
            }
        for ( int i=n+1; i<=n*2; i++ )
            add( ans,Mod-f[n][i]);
    }

    printf( "%lld\n",ans );
    return 0;
}