luogu P3802 小魔女帕琪

​ 题目链接:小魔女帕琪

---

​ 设 \(N\) 为 \(\sum_{i=1}^7{a_i}\) 。我们将本题模型抽象成一个长度为 \(N\) 的序列。我们考虑每个位置作为终极魔法起始点的贡献，由于每个位置作为终极魔法的起点概率是独立的，即不跟其他位置释放的魔法有关，所以我们将每个位置作为终极魔法的起点的贡献累加起来就是答案。

​ 那么每个位置作为终极魔法释放的起点的释放方案个数有：

\[\frac{7\;!\times(N-7)!}{\prod_{i=1}^{7}{（a_i-1）!}} \]

​ 而在序列中能够作为终极魔法释放起点的个数为 \(N-6\) ，将其累加得到式子：

\[\frac{7\;!\times(N-6)!}{\prod_{i=1}^{7}{（a_i-1）!}} \]

​ 意思是，有这么多种序列的排列方式能对答案产生贡献。但是我们注意到，这么多序列里是有重复的，但这并不影响我们统计答案，为什么？被重复计算的序列一定是释放出多个终极魔法的序列，换句话说，这个序列能释放多少次终极魔方他就被多统计了多少次。但是由于我们计算的是每个位置有终极魔法的贡献，而每个终极魔法是独立的所以我们算出来的方案是正确的。你可以这么理解：由于每个终极魔法的贡献是1，而每个序列的贡献却不一定是1，而在我们计算出的方案中每个序列被统计了他的贡献 \(w\) 次，所以有贡献的序列数 \(\times\) 序列的贡献 和有贡献的魔法数 \(\times\) 魔法的贡献的值是相通的。

​ 那么我们的答案就是上述求出的有贡献的方案数，而每个方案数的贡献是1，我们将其相乘除以一个总方案数就得到了答案，公式如下：

\[\begin{align} &=\dfrac{\frac{7\;!\times(N-6)!}{\prod_{i=1}^{7}{(a_i-1)!}}}{\frac{N!}{\prod_{i=1}^{7}{a_i!}}} \\ &=\dfrac{\prod_{i=1}^{7}{a_i}\times7\;!\times(N-6)!}{N!} \\ &=\dfrac{\prod_{i=1}^{7}{a_i}\times7\;!}{\prod_{i=0}^{5}(N-i)} \end{align} \]

​ 答案就是这个公式。代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long double ans;
int n,a[8];
int main()
{
	int n=7;ll tot=0;bool flag=1;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		tot+=a[i];
		if(!a[i]) flag=0;	
	}
	if(!flag)
	{
		printf("0.000\n");
		return 0;
	}
	else
	{
		ans=1.0;
		for(int i=1;i<=7;++i)
			ans=ans*(long double)i;
		for(int i=1;i<=6;++i)
			ans=ans*a[i]/(long double)(tot-i+1);
		ans=ans*(long double)a[7];
	}
	printf("%.3Lf",ans);
	return 0;
}

总结：期望题一定要注意每种贡献序列之间的关系，如果产生贡献的序列比较复杂，我们可以将其拆解成互不相干，独立的序列进行统计累加。