题目概述

字符串对 $(A,B)$ 是相似的需要满足两个串等长，且存在 $C$ 使得 $A+C=C+B$ 。求长度为 $n$ ，出现字母是小写字母前 $K$ 个的相似字符串对的个数。

解题报告

其实马上就想到了，但就是抽风了……考虑一个串，如果把他的某个前缀移到后面，那么显然这两个串就相似。很明显这就是循环同构，所以某个串的方案数就是和他循环同构的串的个数也就是该串最短循环节的长度。

循环节长度肯定是 $n$ 的因子，到这里就想到经典容斥了，考虑到 $n$ 的因子个数并不多，最多是 $1000$ 个左右，所以令 $f_i$ 表示 $n$ 的因子 $i$ 为最短循环节的方案数，那么 $f_i=K^i-\sum_{j|i}f_j$ 。最后答案就是 $\sum_{i|n}i\cdot f_i$ 。

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxm=2000,MOD=1e9+7;

int n,K,m,D[maxm+5],f[maxm+5],ans;

inline void AMOD(int &x,int y) {if ((x+=y)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1,s=sqrt(n);i<=s;i++) if (!(n%i)) {D[++m]=i;if (i<n/i) D[++m]=n/i;}
    sort(D+1,D+1+m);for (int i=1;i<=m;i++) {f[i]=Pow(K,D[i]);for (int j=1;j<i;j++) if (!(D[i]%D[j])) AMOD(f[i],MOD-f[j]);}
    for (int i=1;i<=m;i++) AMOD(ans,(LL)D[i]*f[i]%MOD);printf("%d\n",ans);return 0;
}