大坑待补

我起了，一枪秒了，有什么好说的

又是快乐爆0

Task 1

题淦:

给出n个正整数a1,a2…an和一个质数mod.一个变量x初始为1.进行m次操作.每次在n个数中随机选一个ai,然后x=xai%mod.问m次操作之后x的取值的期望. 答案一定可以表示成a/b的精确分数形式.a和b可能很大,所以只需要输出a(b^(10^9+5))模10^9+7的结果.

【孙金宁教你学数学】

质数P的原根g满足1<=rt<P,且rt的1次方,2次方…(P-1)次方在模P意义下可以取遍1到(P-1)的所有整数.欧拉定理:对于质数P,1<=x<P的任意x的P-1次方在模P意义下都为1.显然,原根的1次方,2次方…（P-2）次方在模P意义下都不为1,只有(P-1)次方在模P意义下为1.这也是一个数成为原根的充分必要条件.

数据范围:

第1个测试点:mod=2 第2个测试点:n=1 第3,4,5个测试点:m<=1000,1<=mod<=300. 第6,7,8个测试点: 1<=mod<=300 对于全部测试点: 1<=ai<mod,mod为质数1<=mod<=1000, 对于全部测试点:1<=n<=10^5,1<=m<=10^9

考试时看到这个 $a*(b^(10^9+5)) mod 10^9+7$就傻了，而且既不知道原根是啥，也不知道原根怎么求，还不知道原根在这题里有什么用，听讲解是发现啥也不会……而且很明显输出1就能拿分的第一个点也没有拿到

SO，考后恶补知识 upd:补了一下午，啥也没干

思路

回来看题干：$ a*(b^(10^9+5) mod 10^9+7 $ 这个玩意涉及到逆元

费马小定理假如p是质数，且gcd(a,p)=1，那么 $ a(p-1)≡1( mod p) $

如果求解 a / b mod m 求 b 的模m乘法逆元，若b， m互质(题目中恰好告诉了你这点) 则 kb mod m = 1 且 b^(m-1) mod m = 1 (必然？)所以 kb = b^(m-1) 可直接得出b的模m乘法逆元为 b ^ (m-2) 因此，这个式子的结果=ab对1e9+7的逆元 mod 10^9+7 (对于样例而言，是3500000004%1000000007)

nb的博客

END OF 费马小定理

可以把所有的a换成%p意义下g(原根)的某次方，这样连乘的计算就可以变成连加。eg:刚开始一个数是a0,你可以从a4,a7,a23里面随机选数把它乘起来，值对mod取模，得到ans，求最后ans的期望。 因此，最后的式子为 $ k0g^0+k1g^1+…+k_(p-1)*g^(p-1) $ k是每一个答案（g的若干次幂）出现的次数，ki的计算，是从n个元素中取m次，取出的数的次方之和等于i。

因为A^x = A^(x % φ(p) + φ(p)) (mod p) (x>=p) 所以如果模数是一质数，在计算快速幂的时候，可以直接把指数%(p-1)

上一行的解释：对每个不是p的倍数的数x，由fermat小定理，x的p-1次方模p余1，由同余的乘法法则，可以把这p-1次方从指数中减掉，如此操作就相当于指数对p-1取了模。

因此，矩阵的大小也为p-1 * p-1

矩阵

base矩阵的构造也很简单，对于每一个可能被选到的数a[i]，枚举乘之前的数j。