牛客33634E - 野兽追猎者塔维什plus

• 链接：https://ac.nowcoder.com/acm/contest/33634/E
• 知识点：概率期望、二项分布
• 难度：蓝

题意

• 动物伙伴总共有三种：

米莎：4点攻击力，2点血量。
雷欧克：2点攻击力，4点血量。
霍弗：4点攻击力，4点血量。

• 每种动物伙伴出现的概率均为 $\frac{1}{3}\backslash frac\{1\}\{3\}$。
• 其中每只 雷欧克 有一个效果：除了该 雷欧克 以外的其他随从获得 $f(x)f(x)$ 的攻击力，$xx$ 为雷欧克的总数。
• $f(x)={\sum }_{i=1}^{10}{a}_i{x}^{i}f(x)=\backslash sum\_\{i=1\}^\{10\}a\_ix^i$
• 现在总共有 $nn$ 个动物伙伴，求攻击力总和的期望值与血量总和的期望值。

思路（血量总和期望值）

利用期望的线性性质。
$ans=\frac{n}{3}\times (2+4+4)ans=\backslash frac\{n\}\{3\}\backslash times\; (2+4+4)$

思路（攻击力总和期望值）

错误思路

• 既然每一种动物出现的概率都是 $\frac{1}{3}\backslash frac\{1\}\{3\}$，
• 那么 雷欧克 出现数量的期望是 $\frac{n}{3}\backslash frac\{n\}\{3\}$，
• 每一只 雷欧克 都能给余下的 $n-1n-1$ 只动物产生总加和为 $(n-1)\times f(\frac{n}{3})(n-1)\; \backslash times\; f(\backslash frac\{n\}\{3\})$ 的攻击力。
• 所以 $ans=\frac{n}{3}\times (4+2+4)+f(\frac{n}{3})ans=\backslash frac\{n\}\{3\}\backslash times\; (4+2+4)+f(\backslash frac\{n\}\{3\})$

错误原因

• 注意看 $f(x)={\sum }_{i=1}^{10}{a}_i{x}^{i}f(x)=\backslash sum\_\{i=1\}^\{10\}a\_ix^i$
• 我们能观察到，$f(x)f(x)$ 不是线性的。

• 举个例子。假如 $a_1=1a\_1=1$，$a_{10}=100000000000a\_\{10\}=100000000000$，
• 并且你不能保证 雷欧克 出现的数量一定是 $\frac{n}{3}\backslash frac\{n\}\{3\}$，
• 那么在这种条件下 $f(\frac{n}{3})f(\backslash frac\{n\}\{3\})$ 是要偏大的。

正确思路

• 注意看 $f(x)={\sum }_{i=1}^{10}{a}_i{x}^{i}f(x)=\backslash sum\_\{i=1\}^\{10\}a\_ix^i$
• 我们只能从 $a_i{x}^{i}a\_ix^i$ 处下手计算。
• 枚举实际 雷欧克 的数量，雷欧克 出现的次数为 $ii$ 的可能性是 $C_n^i\times p^i(1-p_i{)}^{n-i}C\_\{n\}^\{i\}\backslash times\; p^i(1-p\_i)^\{n-i\}$，贡献是 $(n-1)\times {\sum }_{j=1}^{10}(a_j\times i^j)(n-1)\backslash times\; \backslash sum\_\{j=1\}^\{10\}(a\_j\backslash times\; i^j)$
• $ans=\frac{10n}{3}+(n-1)\times {\sum }_{i-1}^n[C_n^i\times p^i(1-p_i{)}^{n-i}\times {\sum }_{j=1}^{10}(a_j\times i^j)]ans=\backslash frac\{10n\}\{3\}+(n-1)\backslash times\; \backslash sum\_\{i-1\}^\{n\}[C\_\{n\}^\{i\}\backslash times\; p^i(1-p\_i)^\{n-i\}\backslash times\; \backslash sum\_\{j=1\}^\{10\}(a\_j\backslash times\; i^j)]$

代码

#include <cstdio>
#include <iostream>
#define int long long
const int N	= 1e6+10;
const int MOD 	= 1e9+7;
using namespace std;

long long bin[N];

void Init()
{
	bin[0]=1; 
	bin[1]=1;
	for(int i=2;i<N;i++)
		bin[i]=i*bin[i-1]%MOD;
}

long long POW(long long a,long long b)
{
	long long ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans*=a;
			ans%=MOD;
		}
		a*=a;
		a%=MOD;
		b>>=1;
	}
	return ans;
}

int Div(int a,int b)
{
	return a*POW(b, MOD-2)%MOD;
}

long long C(long long n, long long m)
{
	return (bin[n]%MOD)*(POW(bin[m]*bin[n-m]%MOD,MOD-2))%MOD;
}

int arr[20];
int n;

void Solve()
{
	int ans = 0;
	int p = Div(1, 3);
	int _p = Div(2, 3);
	for (int i=1; i<=n; i++)
	{
		int tmp = 0;
		for (int j=1; j<=10; j++)
		{
			tmp += arr[j] * POW(i, j) % MOD, tmp%=MOD;
		}
		tmp *= C(n,i) * POW(p, i) %MOD * POW(_p, n-i)%MOD, tmp%=MOD;
		
		ans += tmp, ans%=MOD;
	}
	ans *= (n-1), ans%=MOD;
	ans += Div(10*n, 3), ans%=MOD;
	
	printf("%lld %lld\n",ans,Div(10*n%MOD, 3));
}

signed main()
{
	Init();
	scanf("%lld",&n);
	for (int i=1; i<=10; i++)
	{
		scanf("%lld",&arr[i]);
	}
	Solve();
	return 0;
}