@liu_runda
【题目描述】
给出n个正整数a1,a2…an和一个质数mod.一个变量x初始为1.进行m次操作.每次在n个数中随机选一个ai,然后x=x*ai%mod.问m次操作之后x的取值的期望.
答案一定可以表示成a/b的精确分数形式.a和b可能很大,所以只需要输出a*(b^(10^9+5))模10^9+7的结果.
【输入格式】
第一行三个整数n,m,mod.
接下来一行n个空格隔开的正整数a1,a2…an
【输出格式】
一行一个整数表示答案
【样例输入】
5 1000000000 2
1 1 1 1 1
样例输出】
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
【孙金宁教你学数学】
质数P的原根g：
满足1<=g < P,且g的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.这也是一个数成为原根的充分必要条件.
分析：
重点题
这是一道等概率的问题，我们可以用
总情况/情况数
情况数：n^m
现在的问题就是如何求总情况之和
题目非常良心，给出了原根的性质，同时模数是一个质数
难道这不能给我们一点启发吗
程序一开始我们就求出给出的模数p的原根
原根一般都不会很大，所以枚举即可
同时根据原根的性质，
暴力判断枚举元素的1~p-2次方有没有在%p意义下等于1
int get() //求原根
{
for (int i=2;i<=p;i++)
{
ll tmp=1;
bool flag=1;
for (int j=1;j<p-1;j++)
{
tmp=tmp*i%p;
if (tmp==1)
{
flag=0;
break;
}
}
if (flag) return i;
}
}我们可以把所有的a换成%p意义下g(原根)的某次方
这样连乘的计算就可以变成连加
连乘出来答案也一定是一个g^x的形式
最后的总情况之和的形式：
k是每一个答案（g的若干次幂）出现的次数
ki的计算，说白了就是从n个元素中取m次，取出的数的次方之和等于i
这就是一个经典模型：序列计数
设计矩阵加速
然而
这里又有一个问题需要注意了
费马定理
A^x = A^(x % φ(p) + φ(p)) (mod p) x>=p
简单来说就是如果模数是一质数，在计算快速幂的时候，可以直接把指数%(p-1)
我们的矩阵计算的就是指数之和，
所以关于矩阵的所有模数都是
p-1
这就导致矩阵的大小也变成了p-1*p-1（因为%（p-1））
在计算最后答案的时候，模数是1e9+7
所以说，整个程序中模数有三次变化
- 计算原根以及原根的若干次幂的时候，模数是p
- 计算矩阵的时候，因为计算的是原根的指数和，模数是p-1
- 计算答案的时候，模数是1e9+7
tip
搞明白了之后
我就开始写了，
写完之后就发现已运行就报错
经过一个小时的排查之后，发现是矩阵乘法使用的struct有问题
最后证明是矩阵的大小开大了
因为这个矩阵是循环矩阵
我们只用计算第一行
所以只用开1000即可
时刻注意清零和初始化
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int N=100010;
const ll mod=1000000007;
int n,m,rt,cnt[N],p,lg[N],mi[N],a[N];
ll inv;
struct node{
ll H[1002];
node operator *(const node &a) const
{
node ans;
ans.clear(); //
for (int i=0;i<p-1;i++) //只计算第一行
for (int j=0;j<p-1;j++)
{
ans.H[(i+j)%(p-1)]=ans.H[(i+j)%(p-1)]+H[i]*a.H[j];
if (ans.H[(i+j)%(p-1)]>8e18)
ans.H[(i+j)%(p-1)]%=mod;
}
for (int i=0;i<p-1;i++)
ans.H[i]%=mod;
return ans;
}
void clear()
{
memset(H,0,sizeof(H));
}
node KSM(int pp)
{
node an,a=(*this);
an.clear();
an.H[lg[1]]++;
while (pp)
{
if (pp&1)
an=an*a;
pp>>=1;
a=a*a;
}
return an;
}
};
node H,ans;
ll KSM(ll a,int b,ll p)
{
a%=p;
ll t=1;
while (b)
{
if (b&1)
t=(t%p*a%p)%p;
b>>=1;
a=(a%p*a%p)%p;
}
return t%p;
}
int get() //求原根
{
for (int i=2;i<=p;i++)
{
ll tmp=1;
bool flag=1;
for (int j=1;j<p-1;j++)
{
tmp=tmp*i%p;
if (tmp==1)
{
flag=0;
break;
}
}
if (flag) return i;
}
}
int main()
{
freopen("rand.in","r",stdin);
freopen("rand.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
inv=KSM(KSM((ll)n,m,mod),mod-2,mod); //分母逆元,计算最后答案
rt=get();
if (p==2)
{
printf("1");
return 0;
}
mi[0]=1;
for (int i=1;i<p-1;i++)
{
mi[i]=(mi[i-1]%p*(ll)rt%p)%p; //%p 意义下rt的若干次幂
lg[mi[i]]=i;
}
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
H.H[lg[a[i]]]++; //次方
}
ans=H.KSM(m);
ll sum=0;
for (int i=0;i<p-1;i++) //分子的计算
sum=(sum+(ll)mi[i]*ans.H[i]%mod)%mod;
printf("%lld",sum*inv%mod);
return 0;
}