D. Santa's Bot

2019/12/31 22:48
阅读数 39

题意:圣诞老人收到一些信件来自n个不同的小朋友这年,当然,每个孩子都想要从圣诞老人那得到一些礼物,尤其,第i个小朋友想要ki个不同的礼物中的一个作为他的礼物,一些礼物可能被多个小孩所拥有。

圣诞老人很忙碌,所以他想要新年机器人去选择一些礼物给孩子,不幸的是,机器人算法出了一些Bug,为了选择一些礼物给孩子,机器人执行如下的操作: 1.等概率地从n个孩子中选择孩子x 2.从第x个小孩想要的kx个礼物中等概率地选出y礼物 3.等概率地选择一个小孩z去接受这个礼物 (x, y, x)被叫做机器人的一种选择 如果小孩z列出的礼物中存在y礼物,那么这个选择就是有效的。 计算这个选择有效的概率

输入: 第一行表示n个小孩 接下来n行,第i行表示第i个小孩想要的圣诞礼物列表,ki, ai1, ai2, ... aiki, 一个礼物在同一个列表里不会出现多次

输出: 打印机器人有效选择的概率,把这个概率表示为不可约分数$\frac{x}{y}$,你必须打印$x \cdot{y}^{-1} mod 998244353$

分析:题目的意思是说有n个小孩子,每个孩子有ki件礼物是他们想要的,现在随机地挑出一个孩子去接受这个礼物,并且这个礼物也是存在他想要的礼物单里的询问这个概率 假设我们现在挑出来一个孩子x,挑出他的概率为1 / n,从他的愿望单里选出一个礼物,概率变为1 / n * 1 / k[x],再挑一个孩子,并且符合的概率为:1/n * 1/k[x] * 该礼物的数量(所有愿望单里) / n,这样就可以求得这个概率,然后把所有概率相加,可以得到如下的公式 $\frac{1}{n^2}*\sum_{i = 1}^{n}(\frac{\sum cnt[i][j]}{k[i]})$ 输出要求我们先把这个概率化成不可约的分数x / y,然后求x / y mod 998244353,这个可以采用快速幂求逆元,快速幂求逆元的作用就是把x / y mod p这种形式的东西变成x * q mod p,即把这个除法化成乘法,并且它们相模的值相等 因为,在计算机中除法变成乘法会变得好很多 这是数论的东西,想弄懂这道题必须要有前缀知识:快速幂取模和快速幂求逆元

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

using LL = long long;
const int mod = 998244353;
const int N = 1e6 + 5;
vector<int> list[N];
int k[N];
//记录礼物数量
int cnt[N];
//快速模
LL qmi(int a, int b, int p)
{
	LL res = 1;
	while (b)
	{
		if (b & 1) res = res * a % p;
		a = a * (LL)a % p;
		b >>= 1;//b右移一位
	}
	return res;
}

//费马小定理
//y的模mod的乘法逆元
int Fermat(int y)
{
	return qmi(y, mod - 2, mod);
}

int main()
{
	//n个小孩
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &k[i]);
		list[i].resize(k[i] + 1);
		for (int j = 1; j <= k[i]; ++j)
		{
			scanf("%d", &list[i][j]);
			++cnt[list[i][j]];
		}
	}

	LL res = 0;
	//计算概率

	//只需求1/k[x] * cnt即可
	for (int i = 1; i <= n; ++i)
	{
		LL cur = 0;
		for (int j = 1; j <= k[i]; ++j)
			cur += cnt[list[i][j]];
		//求k[i]模mod的乘法逆元
		res += ((cur % mod) * Fermat(k[i])) % mod;
	}
	//再乘以1 / n * n
	res = ((res % mod)) * Fermat((1ll * n * n) % mod) % mod;

	printf("%lld\n", res);


	return 0;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部