科技网站域名,wordpress 顶 踩,做一个网页一般多少钱,2023年九月份新闻题目#xff1a; 样例解释#xff1a; 【样例 1 解释】 由于在这个样例中#xff0c;对于每组 i,j#xff0c;Emiya 都最多只会做一道菜#xff0c;因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。 符合要求的方案包括#xff1a; 做一道用烹饪方法 1、主要…题目 样例解释 【样例 1 解释】 由于在这个样例中对于每组 i,jEmiya 都最多只会做一道菜因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。 符合要求的方案包括 做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 2 的菜做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 3 的菜做一道用烹饪方法 1、主要食材 3 的菜和一道用烹饪方法 2、主要食材 2 的菜 因此输出结果为 3mod998,244,3533。 需要注意的是所有只包含一道菜的方案都是不符合要求的因为唯一的主要食材在超过一半的菜中出现这不满足 Yazid 的要求。 【样例 2 解释】 Emiya 必须至少做 2 道菜。 做 2 道菜的符合要求的方案数为 100。 做 3 道菜的符合要求的方案数为 90。 因此符合要求的方案数为 100 90 190。 思路 首先考虑列的限制发现若有不合法的列则必然有且只有一列是不合法的因为不可能有不同的两列数量都超过总数的一半。 于是发现列的限制容易容斥计算每行选不超过一个的方案数 - 每行选不超过一个且某一列选了超过一半的方案数。 那么考虑枚举不合法的一列。假设我们已经枚举了不合法的列为colcol接下来会发现我们只关心一个数的位置是否在当前列如果属于在其他列的情况那么它具体在哪一列对当前列的合法性并无影响我们并不需要考虑。 接下来设计状态。fi,j,kfi,j,k表示对于colcol这一列前ii行在colcol列中选了jj个在其他列中选了kk个那么令sisi为第ii行的总和则有转移 fi,j,kfi−1,j,k ai,col∗fi−1,j−1,k (si−ai,col)∗fi−1,j,k−1fi,j,kfi−1,j,k ai,col∗fi−1,j−1,k (si−ai,col)∗fi−1,j,k−1 状态数O(n3)O(n3)转移O(1)O(1)算上枚举colcol这一步复杂度是O(mn3)O(mn3)的。统计如下和式的值并对每一列求和即可得到不合法的方案数 ∑jkfn,j,kjk∑fn,j,k 接下来考虑计算总方案数和之前相似只需设gi,jgi,j为前ii行共选了jj个数的方案数则有转移 gi,jgi−1,j si∗gi−1,j−1gi,jgi−1,j si∗gi−1,j−1 那么∑i1ngn,ii1∑ngn,i就是总方案数 这一步是O(n2)O(n2)的。所以现在可以在O(mn3)O(mn3)的总复杂度内完成这题获得84分。 考虑进一步优化剪去无用状态注意到在不合法情况的计算过程中也就是fi,j,kfi,j,k的转移过程中我们实际上并不关心j,kj,k的具体数值而只关心相对的大小关系所以我们可以将状态变为fi,jfi,j表示前ii行当前列的数比其他列的数多了jj个则有转移 fi,jfi−1,j ai,col∗fi−1,j−1 (si−ai,col)∗fi−1,j1fi,jfi−1,j ai,col∗fi−1,j−1 (si−ai,col)∗fi−1,j1 转移仍然是O(1)O(1)的但总复杂度降为O(mn2)O(mn2)可以通过此题。 代码
1.
#include cstdio
#include cstring
#include algorithm
using namespace std;typedef long long ll;
const int Maxn 100;
const int Maxm 2000;
const int Mod 998244353;int N, M;
int A[Maxn 5][Maxm 5];
int sum[Maxn 5];ll f[Maxn 5][Maxn * 2 5];
ll Solve(int typ) {for(int i 0; i N; i)for(int j 0; j N * 2; j)f[i][j] 0;f[0][N] 1;for(register int i 0; i N; i)for(register int j 0; j N * 2; j) {if(j) f[i 1][j - 1] (f[i 1][j - 1] f[i][j]* (sum[i 1] - A[i 1][typ]) % Mod) % Mod;f[i 1][j] (f[i 1][j] f[i][j]) % Mod;f[i 1][j 1] (f[i 1][j 1] f[i][j]* A[i 1][typ] % Mod) % Mod;}ll ret 0;for(int i N 1; i N * 2; i)ret (ret f[N][i]) % Mod;return ret;
}int main() {
#ifdef LOACLfreopen(in.txt, r, stdin);freopen(out.txt, w, stdout);
#endifscanf(%d %d, N, M);for(int i 1; i N; i)for(int j 1; j M; j)scanf(%d, A[i][j]);ll ans 1;for(int i 1; i N; i) {for(int j 1; j M; j)sum[i] (sum[i] A[i][j]) % Mod;ans ans * (sum[i] 1) % Mod;}ans (ans - 1 Mod) % Mod;for(register int i 1; i M; i)ans (ans - Solve(i) Mod) % Mod;printf(%lld\n, ans);return 0;
}
2.
#include iostream
#include cstdlib
#include cstring
#include cstdio
#define mod 998244353using namespace std;
typedef long long ll;
const int MAXN 105, MAXM 2005;
int n,m,a[MAXN][MAXM],sum[MAXN][MAXM];
ll f[MAXN][MAXN*2],g[MAXN][MAXN];int main()
{cin n m;for(int i 1; in; i)for(int j 1; jm; j){scanf(%d,a[i][j]);sum[i][0] (sum[i][0]a[i][j])%mod;}for(int i 1; in; i)for(int j 1; jm; j)sum[i][j] (sum[i][0]-a[i][j]mod)%mod;ll ans 0;for(int col 1; colm; col){memset(f,0,sizeof(f));f[0][n] 1;for(int i 1; in; i)for(int j n-i; jni; j) f[i][j] (f[i-1][j]f[i-1][j-1]*a[i][col]%modf[i-1][j1]*sum[i][col]%mod)%mod;for(int j 1; jn; j)ans (ansf[n][nj])%mod;}g[0][0] 1;for(int i 1; in; i)for(int j 0; jn; j) g[i][j] (g[i-1][j](j0?g[i-1][j-1]*sum[i][0]%mod:0))%mod;for(int j 1; jn; j)ans (ans-g[n][j]mod)%mod; cout ans*(mod-1)%mod endl;return 0;
}
