首页 > 其他分享 >P5664 [CSP-S2019] Emiya 家今天的饭 题解

P5664 [CSP-S2019] Emiya 家今天的饭 题解

时间:2024-03-21 20:35:30浏览次数:30  
标签:P5664 int 题解 add 一列 ans Emiya include mod

题目链接: P5664 [CSP-S2019] Emiya 家今天的饭

思路:

显然可以算出总数减去不合法的,不合法即有一列超过一半,显然最多一列,枚举这一列。

考虑 dp,设 \(f(i,j,k)\) 表示前 \(i\) 个方法,\(j\) 个这一列,\(k\) 个其他列。

但是这样是 \(O(n^3m)\),我们需要优化。

显然我们只关心 \(j,k\) 相对大小,直接差值 dp 即可。

点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
const int M = 2005;
const int mod = 998244353;

int n, m;
int a[N][M] = {{0}};
int s[N] = {0};

void add(int &x, int y) {
	x = (x + y) % mod;
}

int f[N][N * 2] = {{0}};
int cal(int x) {
	f[0][n] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n * 2; j++) {
			f[i][j] = 0;
			add(f[i][j], f[i - 1][j]);
			if (j > 0)
				add(f[i][j], 1ll * a[i][x] * f[i - 1][j - 1] % mod);
			if (j < n * 2)
				add(f[i][j], 1ll * (s[i] - a[i][x] + mod) % mod * f[i - 1][j + 1] % mod);
		}
	}
	int ans = 0;
	for (int i = n + 1; i <= n * 2; i++)
		add(ans, f[n][i]);
	return ans;
}

int main() {
	cin >> n >> m;
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			add(s[i], a[i][j]);
		}
		ans = 1ll * ans * (s[i] + 1) % mod;
	}
	ans = (ans - 1 + mod) % mod;
	for (int j = 1; j <= m; j++)
		ans = (ans - cal(j) + mod) % mod;
	cout << ans << endl;
	return 0;
}

标签:P5664,int,题解,add,一列,ans,Emiya,include,mod
From: https://www.cnblogs.com/rlc202204/p/18088191

相关文章

  • [CF845G] Shortest Path Problem? 题解
    [CF845G]ShortestPathProblem?题解注意到如果我们在路径中多走了一个环,那么得到的贡献就是这个环的贡献。对于这种有关环的问题,考虑一棵生成树,这样所有环都可以用一条祖先边和一些树边组成,发现选环走的过程是独立的,考虑把所有环的权值丢进线性基里,然后查询xordist[1]^xor......
  • 20240321每日一题题解
    20240321每日一题题解Problem已知\(f(x,n)=\sqrt{n+\sqrt{(n-1)+\sqrt{(n-2)+\sqrt{...+2+\sqrt{1+x}}}}}\)。计算\(f\)的值。输入\(x\)和\(n\)​。输出这个函数值,并且注意需要保留两位小数。例如,输入4.210,则应该输出3.68Solution递归?循环?说实话这道题是有一定思考......
  • P1017 [NOIP2000 提高组] 进制转换题解
    题目我们可以用这样的方式来表示一个十进制数:将每个阿拉伯数字乘以一个以该数字所处位置为指数,以10为底数的幂之和的形式。例如123可表示为1×102+2×101+3×100这样的形式。与之相似的,对二进制数来说,也可表示成每个二进制数码乘以一个以该数字所处位置为指数,以2为底数的幂之......
  • CF1945E Binary Search 题解
    CF1945EBinarySearch题目大意给定一个\(1\simn\)的排列\(A\)(不保证有序),对这个排列用如下代码片段二分,查找\(m\)的位置。intl=1,r=n+1;while(r-l>1){intmid=(l+r)/2;if(A[mid]<=m) l=mid;else r=mid;}cout<<l;显然不一定能查找到正确位置,所以在......
  • 题解 P5809【【模板】多项式复合逆】
    \(\text{Link}\)力求把最新技术翻译地人人都能看懂。推荐先学习:拉格朗日反演。题意给出\(n\)次多项式\(F(x)\),求一个\(n\)次多项式\(G(x)\)满足\(F(G(x))\equivx(\bmodx^{n+1})\)。保证\([x^0]F(x)=0\)且\([x^1]F(x)\ne0\)。\(n\le2\times10^4\)。思路我们......
  • 20240320每日一题题解
    20240320每日一题题解Problem阿克曼(Ackermann)函数\(A(m,n)\)中,\(m,n\)定义域是非负整数(\(m\le3\),\(n\le10\)),函数值定义为:\(\mathit{akm}(m,n)=n+1\);(\(m=0\)时)。\(\mathit{akm}(m,n)=\mathit{akm}(m-1,1)\);(\(m>0\)、\(n=0\)时)。\(\mathit{akm}(m,n)=......
  • CF817F MEX Queries 题解
    题目链接:CF或者洛谷不是很难的题,但在这里提供一个动态开点线段树怎么卡空间卡过去的极致空间处理技巧全局\(mex\)问题,常见的做法就是维护权值树,然后找第一个没有权值的点,可以维护\(\min\),但本题存在第三个操作,所以不能再去传统地维护\(\min或者\max\)去辅助二分了。观......
  • [ARC174B] Bought Review 题解
    【题目描述】你开了一家店,有\(A_i\)个\(i\)星级评论,你可以花费\(P_i\)元买到一个\(i\)星评论,问使得这家店评论的星星平均值不小于\(3\),最少要花多少钱。\(1\lei\le5\)。【思路】首先读入,判断平均值是否小于\(3\),如果大于等于,直接输出\(0\)​然后根据\(3\t......
  • luogu6801题解
    本题解中不区别长度和宽度的区别,它们在本题解中指的是同一个东西。本题解做法用到单调栈。看这个特殊性质好像是让我们在高度上进行研究一下。子任务\(4\)的特殊性质是想让你搞明白在一个矩形中如何计算其内部的矩形个数。下面是一个\(4\times5\)大小的矩形。先来不考......
  • CF1091F 题解
    blog。提供线性做法,各方面完爆反悔贪心。先钦定能不飞就不飞,最后再分配盈余的能量。可能会在飞Lava的时候不够能量,只需要在前面来回移动,刷能量即可。由于Swim比Walk快,所以能Swim就全部用Swim刷能量,不能就Walk。最后是分配盈余能量。显然优先把Walk换成Fly,换一......