主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
int233家坤天的饭
最后更新于 2025-07-31 11:30:43
作者
int233
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
我们先抽象,令 $\Huge b_{i,j}$ 为用第 $\Huge i$ 种烹饪方法,第 $\Huge j$ 种主要食材的做饭的做菜数量 $\Huge \circ$ 显然: $\Huge \forall o\in N^+,1\le o\le n ,\sum b_{o,j}\le1(\mathbb{A})$ $\Huge \forall o\in N^+,1\le o\le m ,\sum b_{j,o}\le [\frac{k}{2}](\mathbb{B})$ 令 $\Huge s_i=\sum\limits_{j=1}^m a_{i,j}$ $\Huge \circ$ 我们考虑容斥,假设如果没有 $\Huge \mathbb{B}$ 的限制,我们显然有 $\Huge dp$ : 令 $\Huge g_{i,j}$ 为进行到第 $\Huge i$ 种烹饪方法,已经做了 $\Huge j$ 个菜的方案数 $\Huge \circ$ 初值:$\Huge g_{0,0}=1$ ,其他全部为 $\Huge 0$ $\Huge \circ$ 转移(注意 `for` 循环的时候要从 $\Huge 0$ 开始):$\Huge g_{i,j}=g_{i-1,j}+g_{i-1,j-1}\times s_i$ 最终的答案为 $\Huge \sum_{i=1}^n g_{n,i}$ $\Huge \circ$ 我们可以计算: $\Huge \sum\limits_{o=1}^m [\sum b_{j,o}>[\frac{k}{2}]]\ge1(\mathbb{C})$ 的方案数,它与 $\mathbb{B}$ 是互斥的 $\Huge \circ$ 因为超过 $\Huge[\frac{k}{2}]$ 的主要食材同时只能有一种,所以我们可以枚举它 $\Huge \circ$ $(\mathbb{D})$ 关于这个超过 $\Huge[\frac{k}{2}]$ 怎么弄,其实我们可以这么干: 枚举 $\Huge\mathbb{D}$ 句话中超限的食材,然后我们记做了一道用这个食材菜为 $\Huge+1$ ,否则记为 $\Huge-1$ ,最终这些记录的值加起来 $\Huge>0$ 时这个食材就超限了 $\Huge \circ$ 根据这个我们可以 $\Huge dp$ : 先枚举那个超限的食材,记为 $Z$ 食材超限,令 $\Huge f_{i,j}$ 表示执行到第 $\Huge i$ 位,目前记录的值为 $\Huge j$ $\Huge \circ$ 初值: $\Huge f_{0,0}=1$ ,其他全为 $\Huge 0$ $\Huge \circ$ 转移: $\Huge f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_{i,Z}+f_{i-1,j+1}\times(s_i-a_{i,Z})$ 最终答案: $\Huge \sum\limits_{i=1}^n f_{n,i}$ ,注意要对 $\Huge j$ 为负数的情况做一些处理。 Code: ```cpp #include<iostream> #include<cstring> using namespace std; typedef long long ll; const ll mod=998244353; ll n,m,a[105][2005],s[105],f[205][205],g[205][2005],ans,tot; int main(){ cin>>n>>m; for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ cin>>a[i][j]; s[i]+=a[i][j]; s[i]%=mod; } } for(ll Z=1;Z<=m;Z++){ memset(f,0,sizeof(f)); f[0][n]=1; for(ll i=1;i<=n;i++){ for(ll j=n-i;j<=n+i;j++){ f[i][j]=f[i-1][j]+f[i-1][j-1]*a[i][Z]%mod+(s[i]-a[i][Z]+mod)%mod*f[i-1][j+1]%mod; f[i][j]%=mod; } } for(ll i=1;i<=n;i++){ ans+=f[n][n+i]; ans%=mod; } } g[0][0]=1; for(ll i=1;i<=n;i++){ for(ll j=0;j<=n;j++){ g[i][j]=g[i-1][j]; if(j>0){ g[i][j]+=g[i-1][j-1]*s[i]%mod; g[i][j]%=mod; } } } tot=mod-ans; for(ll i=1;i<=n;i++){ tot+=g[n][i]; tot%=mod; } cout<<tot%mod; return 0; } ```
正在渲染内容...
点赞
0
收藏
0