达哥T1
实际上还是挺难的，考试时只qj20pts，还qj失败
因为他专门给出了mod的范围，所以我们考虑把mod加入时间复杂度。
$50\%$算法：
考虑最暴力的dp，设$f[i][j]$表示进行$i$次操作后得到的数为$j$,方案总数，转移应该还是很明显的
$dp[i][j*k\%mod]=dp[i-1][j]\timescnt[k]$,$cnt[k]$表示数k出现的次数。
然后在结合前20ptsqj，就可以愉快的拿到50pts。
$100\%$算法：
看题解发现什么原根，矩阵乘，蒟蒻弃疗....
但颓博客时发现remarkable大神写出了倍增优化dp，好像有救了。
根据50分算法，我们可以得到一个性质 $f[i*ii][j*k%mod]=f[i][j]*f[ii][k]$蒟蒻博主并不会证
那么$f[i^2][j*K\%mod]=f[i][j]*f[i][k]$ ,这样我们可以处理出$f[i]$,$f[i^2]$,$f[i^4]$,$f[i^8]$....
这样我们根据二进制拆分思想，可以求出ans。
其实这个过程类似于快速幂。
把快速幂模板中的变量换成数组即可。
最后使用滚动数组省空间。
之前没有做过倍增优化dp的题，这道题就当熟悉套路吧。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #define int long long
7 const int P=1000000007;
8 const int M=1005;
9 using namespace std;
10 int n,m,mod,wi;
11 int now1=1,now2=1,last1,last2;
12 int cnt[M],f[2][M],g[2][M],a[100005];
13 int qpow(int a,int b,int p){
14 int ans=1;
15 while(b){
16 if(b&1) ans=ans*a%p;
17 b>>=1;
18 a=a*a%p;
19 }
20 return ans%p;
21 }
22 void solve(int x){
23 while(x){
24 //cout<<x<<endl;
25 if(x&1){
26 memset(g[now1],0,sizeof(g[now1]));
27 for(int i=1;i<mod;i++) for(int j=1;j<mod;j++) g[now1][i*j%mod]=(g[now1][i*j%mod]+g[last1][j]*f[last2][i])%P;
28 now1=last1,last1^=1;
29 }
30 x>>=1;
31 memset(f[now2],0,sizeof(f[now2]));
32 for(int i=1;i<mod;i++) for(int j=1;j<mod;j++) f[now2][i*j%mod]=(f[now2][i*j%mod]+f[last2][i]*f[last2][j])%P;
33 now2=last2,last2^=1;
34 }
35 return ;
36 }
37 signed main(){
38 scanf("%lld%lld%lld",&n,&m,&mod);
39 for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);cnt[a[i]]++;}
40 for(int i=1;i<mod;i++) f[0][i]=cnt[i];
41 g[0][1]=1;
42 solve(m);
43 int Griezmman=qpow(qpow(n,m,P),P-2,P)%P,ans=0;
44 //cout<<Griezmman<<endl;
45 for(int i=1;i<mod;i++) ans=(ans+g[last1][i]*i)%P;
46 //cout<<ans<<endl;
47 ans=ans*Griezmman%P;
48 printf("%lld",ans);
49 }
View Code