达哥T1
实际上还是挺难的，考试时只qj20pts，还qj失败
因为他专门给出了mod的范围，所以我们考虑把mod加入时间复杂度。
$50\%$算法：
考虑最暴力的dp，设$f[i][j]$表示进行$i$次操作后得到的数为$j$,方案总数，转移应该还是很明显的
$dp[i][j*k\%mod]=dp[i-1][j]×cnt[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 }