题解 | 擅长解密的小红同学（其实是一个错位相减）

关于这个题，我看了一部分人的解释，快速幂和逆元这些是比较重要的一个板子，我建议大家及时的记住到考场上套板子就好。

然后我想主要说一下关于这个题的关键内容：其实是一个高中数学问题{

首先，我们来看排列组合这一步：

如果 我给你三个数 3 1 3，你随便排最多有几个数？

高中老师都会这样说，你不要排3，你要去排1，1有3种情况，那么就会有三个数。

其本质上是因为两个3会算重复，也就是说3*2*1这种计算必然有重复

但是这种高中老师的排1方法是不能应用到计算机的，比如我给你一个这样的情况：

3个2，2个1。这时候你并不能够排1来解决这个问题。

所以我们要寻找普适规律：

所以我们就再想 如果3*2*1是有重复的，我们能不能去重。

3*2*1/2*1*1其实就是3；

同理 5*4*3*2*1/3！*2！，从而就可以得到上面大佬所给的一个公式。

这样的计算，我在后期写题解写起来很容易就出来，但其实我在做这道题的时候是尝试了几次才得出来的，ACM题规律你只要会用就行，哪怕你是猜的都没问题，不需要你考场上现场证明。

第二个求期望(其本质上是一个错位相减){

我们来这么说：

如果你是第二次才出来，第三次猜出来都无所谓，因为p概率是不变的。

那么问题就来了：

第一次才出来是p

第二次猜出来是 （1-p）*p

第三次很显然是 (1-p)*(1-p)*p

第k次呢显然(1-p)^(k-1)*p

我们发现其实最后这个p我们是能提出来的，也就是说最后成为了p*((1-p)+(1-p)^2+(1-p)^3........一直+到(1-p)^(k-1))

如果求期望很显然就是在每个概率之前乘以一个次数：这样就成了一个E(X)= p*(i=1∑i=k) i*(1-p)^(i-1)很显然后面就是一个等差乘以等比的形式

对于这样的错位相减，其实它的求和是有通式的:这里给出

对于(an+b)*q^(n-1) 有Sn=(An+B)*q^n-B

其中 A=a/(q-1) B=(b-A)/(q-1); 本质上成了一个 i趋于无穷时 这个函数的极限

最后不要忘了乘以最前面的那个p哦 算出来期望就是1/p