使用c++设计:有一个数组a有n个元素,把数组中的0等概率替换成1~m的某个数,计算第k个位置的数,就是ak,计算ak的期望,并对结果mod998244353,输入是n,m,k,以及数组的n个值
时间: 2023-05-29 07:02:14 浏览: 57
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define mod 998244353
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
int *a = (int *) malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int c1 = 0, c0 = 0;
srand((unsigned) time(NULL));
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
if (rand() % 2 == 1) {
a[i] = rand() % m + 1;
c1++;
} else {
c0++;
}
}
}
int *cnt = (int *) calloc(m + 1, sizeof(int));
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
}
int f[m + 1];
f[0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = c1; j >= cnt[i]; j--) {
f[j] = (f[j] + f[j - cnt[i]]) % mod;
}
}
int ans = 0;
for (int i = k - c0; i <= c1; i++) {
if (i < 0 || i > m) {
continue;
}
ans = (ans + (long long) f[i] * (m - i + 1)) % mod;
}
printf("%d\n", ans);
free(a);
free(cnt);
return 0;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)