题解 P5664 【Emiya 家今天的饭【民间数据】】

· · 题解

这题骗分还是很简单的。然而我考场上依然花了1小时47分钟才打出64分解法。

先说最简单的骗分解法。因为emiya的朋友有两个限制，一是每行只取一个。这个好办，枚举即可。讨厌的是第二个限制。限制了每种菜的数量，于是最朴素的方法就是直接大力记录每种菜有几个。一看数据，诶？64分都只有3个菜，我去，直接开四维dp，dp[i][m1][m2][m3],表示枚举到第i行，三种菜分别用了几种的方案数。

有转移方程dp[i][m1][m2][m3] =

             dp[i-1][m1-1][m2][m3]*a[i][1]

                +dp[i-1][m1][m2-1][m3]*a[i][2]

            +dp[i-1][m1][m2][m3-1]*a[i][3];

好了接下来说虐心的正解，如果要想出正解就要忘掉64分解法，因为我就受64分解法影响因而一直无法想出正解。

定义：

限制一：每行取一个

限制二：每种菜不超过k/2

这题最巧妙的地方就是限制二为不超过k/2，因为这就意味着如果有一个菜超过了k/2，那么就不可能有其他菜也超过k/2。也就是说可以通过枚举哪一种菜超过了限制而枚举出所有非法方案。

这样，我们可以先用乘法原理直接算出满限制一的方案数。然后分别减去满足限制一但不满足限制二的方案数。

那怎么枚举呢？

当然可以开m+1维dp大力枚举，但是这就是64分解法。

所以要压缩状态。

压缩一：

假如枚举第c种菜，那么我就不关心其他菜具体选了多少，而是只要知道总共选了多少就行了，因此之前的m维直接压缩成2维，一维记录c选了几个，另一维记录其他菜选了几个。

f[i][j][k] = f[i-1][j][k] + f[i-1][j][k-1] (s[i]-a[i][c]) + f[i-1][j-1][k] a[i][c];

复杂度O（mn^3），卡卡常数可以得84分高分。

压缩二：

我发现我好像也不关心c菜数量j与其他菜数量k具体是多少，我只关心：

j>(j+k)/2

如果满足这个关系那么方案就是非法的。

所以变变型就得到：

j-k > 0

好了，不需要三维了，后两维就压成一维就够了

上代码

//ParseIn 是读入函数 
//Core 是核心算法 
//calc_illegal_84 是84分解法 
//calc_illegal_100  是100分解法

#include <cstdio>
#include <iostream>
#include <memory.h>
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define ll long long

using namespace std;

ll n,m;
ll a[110][2010];
ll s[110];
ll f[110][110][110];
ll g[110][210];
ll tot;
ll p = 998244353;

void ParseIn(){
    tot=1;
    scanf("%lld %lld",&n,&m);
    rep(i,1,n){
        rep(j,1,m){
            scanf("%lld",&a[i][j]);
            s[i] += a[i][j];
            s[i] %= p;
        }
        tot *= s[i]+1;
        tot %= p;
    }
    tot = (tot+p-1)%p;
}

void Initialize(){
    rep(i,1,n){
        rep(j,1,m){
            s[i] += a[i][j];
            s[i] %= p;
        }
    }
    tot=1;
    rep(i,1,n){
        tot *= (s[i]+1);
        tot %= p; 
    }
    tot = (tot+p-1)%p;
}

void Display(int i);

//O(mn^3)解法。 
void calc_illegal_84(int ilg){
    memset(f,0,sizeof(f));
    f[0][0][0] = 1;

    rep(i,1,n){
        rep(j,0,i){
            rep(k,0,i){
                f[i][j][k] += f[i-1][j][k];                            //啥也不选,ilg没有变化，其他数量也没有变化 
                if(k!=0)                        
                    f[i][j][k] += f[i-1][j][k-1] * (s[i]-a[i][ilg]);   //选其他  ilg 没有变化，其他数量加一 
                f[i][j][k] %= p;
                if(j!=0)
                    f[i][j][k] += f[i-1][j-1][k] * a[i][ilg];          //选当前非法ilg ilg数量加一，其他数量不变 
                f[i][j][k] %= p;
            }
        }
    }

    rep(j,1,n){
        rep(k,0,n){
            if(j>(j+k)/2){
                tot = (tot+p-f[n][j][k])%p;
            }
        }
    }
}

//对于84分解法，j > (j+k)/2  <=>  j-k>0, 状态可以压缩为数量差 
//g[i][j-k+n] == f[i][j][k], 
void calc_illegal_100(int ilg){
    g[0][n] = 1;   

    rep(i,1,n){
        rep(j,1,n*2){
            g[i][j] = 0;
            g[i][j] += g[i-1][j];
            g[i][j] += g[i-1][j+1] * (s[i]-a[i][ilg]);
            g[i][j] %= p;
            g[i][j] += g[i-1][j-1] * a[i][ilg];
            g[i][j] %= p;
        }
    }
    rep(j,n+1,n*2){
        tot = (tot+p-g[n][j])%p;
    }
}

void Display(int i){
    printf("%d\n",i);
    rep(j,0,n){
        rep(k,0,n){
            printf("%lld ",f[i][j][k]);
        }
        printf("\n");
    }
}

//这里不调用函数是因为卡常数。 
void Core(){
    //printf("%lld\n",tot);
    g[0][n] = 1;
    rep(ilg,1,m){
        rep(i,1,n){
            rep(j,n-i,n+i){
                g[i][j] = 0;
                g[i][j] += g[i-1][j];
                g[i][j] += g[i-1][j+1] * (s[i]-a[i][ilg]);
                g[i][j] %= p;
                g[i][j] += g[i-1][j-1] * a[i][ilg];
                g[i][j] %= p;
            }
        }
        rep(j,n+1,n*2){
            tot = (tot+p-g[n][j])%p;
        }
    }   
    printf("%lld\n",tot);
}

int main(){
    ParseIn();
    Core();
    return 0;
}