枚举$a$和$b$出现的次数，问题即求
$$
A_{i,j}=sum_{p=0}^{L}sum_{q=0}^{L-p}[nmid (p-i)][nmid (q-j)]{Lchoose p}{L-pchoose q}(k-2)^{L-(p+q)}
$$
考虑单位根反演，即$[nmid i]=frac{sum_{k=0}^{n-1}omega^{ik}}{n}$（其中$omega=g^{frac{P-1}{n}}$，$g$为$P$的原根），代入后也即
$$
sum_{p=0}^{L}sum_{q=0}^{L-p}frac{sum_{x=0}^{n-1}omega^{(p-i)x}}{n}frac{sum_{y=0}^{n-1}omega^{(q-j)y}}{n}{Lchoose p}{L-pchoose q}(k-2)^{L-(p+q)}
$$
将其整理并调换枚举顺序，即
$$
frac{1}{n^{2}}sum_{x=0}^{n-1}sum_{y=0}^{n-1}frac{1}{omega^{ix}}frac{1}{omega^{jy}}sum_{p=0}{Lchoose p}(omega^{x})^{p}sum_{q=0}^{L-p}{L-pchoose q}(k-2)^{(L-p)-q}
$$
根据二项式定理，即
$$
frac{1}{n^{2}}sum_{x=0}^{n-1}sum_{y=0}^{n-1}frac{1}{omega^{ix}}frac{1}{omega^{jy}}(omega^{x}+{omega^{y}}+k-2)^{L}
$$
类似于生成函数，考虑构造矩阵，即
$$
egin{cases}X_{i,j}=Y_{i,j}=frac{1}{omega^{ij}}\V_{i,j}=frac{1}{n^{2}}(omega^{i}+omega^{j}+k-2)^{L}end{cases}
$$
（$i$和$j$的范围都是$[0,n)$，即矩阵大小为$n imes n$）
根据式子不难得到$A=XVY$，矩阵乘法计算即可
（另外关于$P$的原根$g$，不难暴力得到$g=13$成立）
时间复杂度为$o(n^{2}log L+n^{3})$（前者为快速幂），可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 505 4 #define mod 1000000009 5 #define ll long long 6 int t,m,n,g,invg,ans,A[N][N],X[N][N],V[N][N],Y[N][N]; 7 ll L; 8 int qpow(int n,ll m){ 9 int s=n,ans=1; 10 while (m){ 11 if (m&1)ans=(ll)ans*s%mod; 12 s=(ll)s*s%mod; 13 m>>=1; 14 } 15 return ans; 16 } 17 int main(){ 18 scanf("%d",&t); 19 while (t--){ 20 scanf("%d%lld%d",&m,&L,&n); 21 g=qpow(13,(mod-1)/n); 22 invg=qpow(g,mod-2); 23 for(int i=0;i<n;i++) 24 for(int j=0;j<n;j++){ 25 A[i][j]=0; 26 X[i][j]=Y[i][j]=qpow(invg,i*j); 27 V[i][j]=(ll)qpow(n*n,mod-2)*qpow((qpow(g,i)+qpow(g,j)+m-2)%mod,L)%mod; 28 } 29 for(int i=0;i<n;i++) 30 for(int j=0;j<n;j++) 31 for(int k=0;k<n;k++)A[i][j]=(A[i][j]+(ll)X[i][k]*V[k][j])%mod; 32 for(int i=0;i<n;i++) 33 for(int j=0;j<n;j++){ 34 ans=0; 35 for(int k=0;k<n;k++)ans=(ans+(ll)A[i][k]*Y[k][j])%mod; 36 printf("%d",ans); 37 if (j!=n-1)printf(" "); 38 else printf(" "); 39 } 40 } 41 return 0; 42 }
View Code
Si vous envisagez d’utiliser une application d’espionnage de téléphone portable, vous avez fait le bon choix.
Lorsque vous avez des doutes sur les activités de vos enfants ou sur la sécurité de leurs parents, vous pouvez pirater leurs téléphones Android à partir de votre ordinateur ou appareil mobile pour assurer leur sécurité. Personne ne peut surveiller 24 heures sur 24, mais il existe un logiciel d’espionnage professionnel qui peut secrètement surveiller les activités des téléphones Android sans les en informer.