题面
题意:
你有K个字母，你需要用K个字母组成L长度的字符串，定义对于该字符串的任意前缀P 必须满足 ，输出方案数%1000000007的值。
思路:
首先可以想到一种简单的dp方程 dp [ len ] [ a ] [b ] 表示当前字符串长度为len 个数为最多的字母有 a个 个数次多的有b个 (那么个数最少的有k-a-b个)状态数有 100*100，没办法矩阵快速幂加速dp.
考虑对于某个固定长度 len 如果确定 a，容易发现 b = (len % K - a)， 发现dp方程可以转化成 dp[ len ] [ a ] 但是依旧不能矩阵快速幂 ，因为对于len-1到len的 每个状态 a 的转移方程的系数与 len%K 相关，
于是稍微转换一下方程 由 len-K 转移到 len (每次放K个字符 ),这时候容易发现 转移方程的系数也不在改变了 于是我们先预处理放K步的dp方程的系数矩阵 然后转移L/K次 （利用矩阵快速幂加速)，最后剩下L%K步暴力dp就好了
(参考了别人的题解)
代码:
#include <stdio.h> #include <bits/stdc++.h> #define IV inline void typedef unsigned long long ull; using namespace std; const int mod = 1e9+7; ull dp[110][110][110],B[110][110],A[110][110],C[110][110]; int K,t; IV DP(int L) { for (int len=1;len<=L;len++){ for (int i=0;i<K;i++){ for (int j=1;j<=K;j++){ int w=3*K+len-1; int l2=w-2*(j-1); while (l2+(j-1)>K)l2-=K; if (l2>=0)dp[len][i][j%K]+=dp[len-1][i][j-1]*(l2); if (j==1&&l2>=0)dp[len][i][j%K]+=dp[len-1][i][l2]*(l2); l2=w-2*j; while (l2+j>K)l2-=K; int l3=K-j-l2; if (l2>=0&&l3>=0)dp[len][i][j%K]+=dp[len-1][i][j%K]*(l3); dp[len][i][j%K]%=mod; } } } } IV init() { memset(dp,0,sizeof(dp)); memset(B,0,sizeof(B)); B[0][0]=1; for (int i=0;i<K;i++)dp[0][i][i]=1; DP(K); for (int i=0;i<K;i++)for (int j=0;j<K;j++)A[i][j]=dp[K][i][j]; } IV mul(ull A[][110],ull B[][110]) { memset(C,0,sizeof(C)); for (int i=0;i<K;i++) for (int j=0;j<K;j++) for (int k=0;k<K;k++) C[i][k]=(C[i][k]+A[i][j]*B[j][k])%mod; memcpy(A,C,sizeof(C)); } IV pow(long long n) { while (n){ if (n&1)mul(B,A); mul(A,A); n>>=1; } } int main() { long long n,ans; scanf("%d",&t); while (t--&&~scanf("%lld%d",&n,&K)){ ans=0; init(); pow(n/K); memset(dp,0,sizeof(dp)); for (int i=0;i<K;i++) for (int j=0;j<K;j++) dp[0][i][j]=B[i][j]; DP(n%K); int L=n%K; for (int j=0;j<K;j++)ans+=dp[L][0][j]; printf("%lld\n",ans%mod); } return 0; }