CSP2019 Emiya 家今天的饭 题解
2024-10-20 02:53:12
这题在考场上只会O(n^3 m),拿了84分。。
先讲84分,考虑容斥,用总方案减去不合法方案,也就是枚举每一种食材,求用它做超过\(\lfloor \frac{k}{2} \rfloor\) 道菜的方案数,从总方案中减去。
先枚举一种食材x,设f[i][j][k]为前i种烹饪方法中,做j道菜,其中k道是食材x做的的方案数,转移考虑第i种烹饪方案 不做菜/做食材x的菜/做其他食材的菜 三种情况。最后所有f[n][j][j/2+1 ~ n]的和即是不合法情况。
考虑怎么优化,设一种方案中有k道菜,其中t道菜是x食材做的,那么当且仅当\(t>\lfloor \frac{k}{2}\rfloor\)时方案不合法,也即\(2t-k>0\)时不合法。那么我们在dp时就只需要记录方案中\(2t-k\)的值,最后取大于0的状态的方案数即可。即设f[i][j]为只考虑前i种烹饪方法,方案中\(2t-k\)的值为j的方案数。转移考虑以上三种情况分别转移到 f[i+1][j]/f[i+1][j+1]/f[i+1][j-1] 即可。
代码:
#include<bits/stdc++.h>
using namespace std;
#define N 107
#define M 2007
#define ll long long
const ll mod=998244353;
ll a[N][M],sum[N],f[N][N<<1];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%lld",&a[i][j]);
sum[i]=(sum[i]+a[i][j])%mod;
}
ll ans=0;
for(int now=1;now<=m;now++)
{
memset(f,0,sizeof(f));
f[0][N]=1;
for(int i=1;i<=n;i++)
{
for(int j=N-n;j<=N+n;j++)
{
f[i][j]=(f[i][j]+f[i-1][j])%mod;
f[i][j]=(f[i][j]+f[i-1][j-1]*a[i][now])%mod;
f[i][j]=(f[i][j]+f[i-1][j+1]*(sum[i]+mod-a[i][now]))%mod;
}
}
for(int i=1;i<=n;i++)
ans=(ans+f[n][N+i])%mod;
}
ll res=1;
for(int i=1;i<=n;i++)
res=res*(sum[i]+1)%mod;
res=(res+mod-1)%mod;
res=(res+mod-ans)%mod;
printf("%lld\n",res);
return 0;
}
最新文章
- 离散信源的分类和数学模型&;&;离散无记忆信源的熵
- CentOS 6 安装 MySQL-python
- android studio 应用小知识总结
- 基因变异(codevs 3194)
- 20141128--JavaScript HTML DOM
- R语言 决策树算法
- PHP的高并发和大数据处理
- Python-Blog1-搭建开发环境
- opencv基础教程 之 图像基础和绘图
- Linux 部署 xxl-job 注意问题
- HDU - 2604 Queuing(递推式+矩阵快速幂)
- .NET基金会成立
- vue父组件为子组件传值传不过去?vue为数组传值,不能直接用等于的方式,要用循环加push的方式
- 【记录】HTTP协议状态码含义
- js数组乱序输出 数组乱序排列
- Linux 的su 与sudo 的区别,查看所有用户
- Gradle Goodness: Automatic Clean Tasks
- CAShapeLayer使用
- Android N 新特性
- 八大排序算法的python实现(四)快速排序
热门文章
- vuex 源码解析(四) mutation 详解
- 关于vue-cli3中配置请求跨域的问题
- Python自动抢红包,超详细教程,再也不会错过微信红包了!
- 一文教您如何通过 Docker 搭建反向代理 Ngnix,并配置 Https SSL 证书
- Python【day 12】生成器和推导式
- 跨域问题 Blocked a frame with origin ";http://......"; from accessing a cross-origin frame.
- mvc 返回json格式时间格式化
- addEventListener和JavaScript的事件机制
- redis的对象
- matlab 基础语法