[CSP-S 2019] Emiya 家今天的饭

知识点

动态规划、容斥原理、计数

解题思路

先算只限制烹饪方法不同的非空方案：各行可不选，或从该行任意食材中选一道，得到product(1+行和)-1。再逐列扣除该食材占严格多数的坏方案。对固定食材，用差值d=该食材菜数-其余菜数做DP；每行有不选、选该食材、选其他食材三类转移，权重分别为1、a[i][j]、行和-a[i][j]。最后d>0的方案均为坏方案。

正确性说明

每个合法选择在逐行DP中有唯一对应，且权重乘积恰计入具体菜品的选择数。违反“一半”要求等价于某列食材严格超过总菜数一半；两种食材不可能同时严格超过一半，因此各列坏事件互不相交，可直接从总数中扣除，不需要更高阶交集。

易错点

总数要减去空方案；d=0合法，不能扣除；行和及乘法用64位并及时取模；负数减法要归一到模数范围。

复杂度

时间O(mn²)，空间O(nm+n)，DP滚动空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
const long long MOD=998244353;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<long long>>a(n,vector<long long>(m));vector<long long>s(n);long long ans=1;for(int i=0;i<n;++i){for(auto&x:a[i]){cin>>x;s[i]=(s[i]+x)%MOD;}ans=ans*(s[i]+1)%MOD;}ans=(ans+MOD-1)%MOD;
 for(int j=0;j<m;++j){vector<long long>dp(2*n+3),ndp(2*n+3);int off=n+1;dp[off]=1;for(int i=0;i<n;++i){fill(ndp.begin(),ndp.end(),0);long long other=(s[i]-a[i][j]+MOD)%MOD;for(int d=-i;d<=i;++d){long long v=dp[off+d];ndp[off+d]=(ndp[off+d]+v)%MOD;ndp[off+d+1]=(ndp[off+d+1]+v*a[i][j])%MOD;ndp[off+d-1]=(ndp[off+d-1]+v*other)%MOD;}dp.swap(ndp);}for(int d=1;d<=n;++d)ans=(ans-dp[off+d]+MOD)%MOD;}cout<<ans<<'\n';}