codeforces786E的解法
时间: 2023-03-07 17:19:48 浏览: 122
Codeforces 786E是一道组合数学的题目。
题目大意是这样的:给定两个长度分别为 $n$ 和 $m$ 的非负整数序列 $a$ 和 $b$,要求你构造一个序列 $c$,使得:
- $c$ 的长度为 $n+m$。
- $c_i$ 的值在 $a$ 和 $b$ 中出现的次数之和的组合数中,下标为 $i$ 的项的系数不为 $0$。
答案对 $998244353$ 取模。
解法:
首先,我们可以用组合数的递推式 $C_{n+1}^{k}=C_n^k+C_n^{k-1}$ 来计算组合数。这样,我们就可以在 $O(nm)$ 的时间内预处理出所有的组合数。
然后,我们可以对 $a$ 和 $b$ 中的每一个数进行枚举,并计算出它在组合数中的系数。
最后,我们可以对 $c$ 进行枚举,并累加出它的值。
总的时间复杂度为 $O(nm)$。
代码如下:
```
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m;
int a[100005],b[100005];
long long c[200005];
long long C[200005][200005];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
//预处理组合数
C[0][0]=1;
for(int i=1;i<=n+m;i