2021CCPC省赛 使用技能

ZZULIOJ 小辣在玩奇怪的的小游戏。

在之前的关卡中，主角收集到了很多的金币，这一关的任务是击败BOSS。

在前面的游戏中，主角收集了m种技能，在攻击BOSS的时候，主角有n次选择技能的机会，在每次选择技能时，主角会从他已经收集的技能中等概率随机选择一个加入技能使用序列中，每种技能可以被多次加入使用序列。

在技能选择完成后，主角获得了一个长度为n的技能使用序列，此时，主角会将n个技能全部施放，随后会对于每种技能进行伤害的结算，对于第i个技能，如果该技能被施放了x次，将会对BOSS造成$x^2$点伤害(如果一个技能从未被施放，那么将不会对BOSS造成伤害)。

小辣现在想知道对于所有可能的技能选择结果，他可以期望对BOSS造成多少点伤害，请输出答案对109+7取模的结果。

第一行输入一个正整数1≤T≤10,表示数据组数。

对于每组数据：

输入一行两个正整数$nm(1\le n\le 10^5,1\le m\le 10^7)$,代表技能序列的长度和技能的种类数。

对于每组数据，输出一行一个正整数，表示技能序列伤害值的期望对$10^9+7$取模的值。

2
5 4
8 4

10
22

思路

求期望, 那就需要一个概率分母, 这里分母就是 所有选择情况 $m^n$, 分子则从技能选择入手, 假如某个技能选 i 个其方案为 $C_n^i$ , 剩下的位置是$(m-1{)}^{n-1}$, 再乘上期望值也就是伤害$i^2\ast m$这里的m是指所有技能的伤害总量, 共有m种技能所以乘m。

那么结果就是$C_n^i\ast (m-1{)}^{n-1}\ast i^2\ast m$ 取模 $1e9+7$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#define int long long
using namespace std;
const int N = 1e5 + 10, M = 1e7 + 10, mod = 1e9 + 7;
int n, m, T;
int fact[N], infact[N];
 
int C(int a, int b)
{
	return fact[a] * infact[b] % mod * infact[a - b] % mod;
}
 
int qmi(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
 
main()
{
	cin >> T;
	fact[0] = 1, infact[0] = 1;
	for (int i = 1; i < N; i++)
	{
		fact[i] = fact[i - 1] * i % mod;
		infact[i] = infact[i - 1] * qmi(i, mod - 2) % mod;
	}
	while (T--)
	{
		cin >> n >> m;
		int res = 0;
		for (int i = 1; i <= n; i++)
		{
			res = (res + m % mod * C(n, i) % mod * qmi(m - 1, n - i) % mod * i % mod * i % mod) % mod;
			// cout << res << " " << C(n, i) % mod << " " << qmi(m - 1, n - i) << endl;
		}
		res = res * qmi(qmi(m, n) % mod, mod - 2) % mod;
		cout << res << endl;
	}
 
	return 0;
}