？？？

神秘性质数数题。

Descr

对于一个字符串，若其每个字符出现不超过 $2$ 次，则称其是 $\operatorname{beautiful}$ 的。

共有 $k$ 种字符，字符串 $S$ 长为 $n$，$T$ 长为 $m$，定义 $f(S,T)$ 为 $T$ 在 $S$ 中不重叠出现的次数。求：

Sol

看到字符串 $T$ 这么奇怪，肯定先从 $T$ 入手。尝试发掘一下 $T$ 的性质。

注意到 $f(S,T)$ 和字符串匹配的规则有些相似，不妨从 $T$ 的 的 $\operatorname{border}$ 发掘一下。

Observation

若 $T$ 有 $\operatorname{border}$，则其有且仅有这一个 $\operatorname{border}$。

简要说明一下，若其有两个或以上的 $\operatorname{border}$，容易发现其第一个字符出现超过 $2$ 次。

所以我们可以把一个 $T$ 唯一地表示为 $wxw$ 的形式，其中 $w,x$ 为字符串。

Corollary

若 $T$ 有 $\operatorname{border}$，则其内部的 $x$ 无论取什么字符串，都不能形成新的 $\operatorname{border}$。

若形成，则有两个 $\operatorname{border}$，与上面的 Observation 矛盾。

很好！我们现在发现了两条非常有用的性质！！1

然而，怎么用是个关键。

先确定一下思路，我们对于每个固定的 $w$ 的长度，计算出有多少种 $T$ 是 $\operatorname{beautiful}$ 的，然后让其跟所有的 $S$ 匹配。

现在让我们考虑这个问题的简单版（这往往十分有效）：假如 $T$ 没有 $\operatorname{border}$，那么怎么求出 $\sum_S f(S,T)$？

Claim

若 $T$ 没有 $\operatorname{border}$，则有：

乍一看没什么问题，$T$ 在 $S$ 中出现的位置有 $n-m+1$ 种，剩下的位置随便填有 $k^{n-m}$ 种方案，乘起来就对了。

仔细一看，其实也没什么问题。当 $T$ 在 $S$ 中多次出现的时候也能够被正确计算，原因是：若 $T$ 在 $S$ 中出现多次，则其在每一次出现的时候都会被算上一次贡献。

现在，若 $T$ 有 $\operatorname{border}$ 该怎么办呢？

我们使用容斥原理。$T=wxw$，则当 $wxwxw$ 出现的时候 $T$ 会被算两次，实则应该算一次，所以减去 $wxwxw$ 出现时的答案。然后我们发现当 $wxwxwxw$ 出现时会被减两次，所以我们再加回来……

一直这么做下去，直到长度超过了 $m$ 停止，就是对的。

现在来到了相对最难的部分：如何对于每个固定的 $w$ 的长度，计算出有多少种 $T$ 是 $\operatorname{beautiful}$ 的。

既然 $w$ 固定后 $x$ 无论怎么填都不会有新的 $\operatorname{border}$，那么不妨转变为算 $x$ 的方案数。

具体地，设 $f_{i,j}$ 为长度为 $i$，字符种数为 $j$ 的 $x$ 有多少种，不难发现 $x$ 也是 $\operatorname{beautiful}$ 的。

先别急着想转移，我需要先明确一下，我们在 DP 的时候不考虑里面的字符具体填的是什么，我们只关心这个长为 $i$ 的字符串哪个位置和哪个位置的字符相同。所以我们有：

为什么呢？

首先 $f_{i,j}=f_{i-1,j-1}$ 是显然的，因为我们直接把新增的那一种字符放到最后即可。

那怎么解释 $(i-1)f_{i-2,j-1}$ 呢？？不难发现这种情况其实是当前字符出现了两次，我们把这两次的其中一次放到末尾，另外一次在前面 $i-2$ 个字符旁的 $i-1$ 个间隙选一个插入即可。

聪明的小伙伴可能就会发现了：为什么必须要把其中一个放在最后呢？？？

其实这很好解释，如果没放在最后，那最后的一定是只出现一次的字符，那就已经包含在第一种情况了。

最后我们考虑给 $x$ 填上字符，让它变成有血有肉的 $\operatorname{beautiful}$ 的字符串！只要给 $f_{i,j}$ 乘上 $P_k^j$ 就可以了！

那么对于长为 $m$ 的 $T$ 呢？我们固定了 $w$ 的长度，然后枚举 $x$ 的字符种类数 $c$，我们直接把前面一半 $w$ 放到 $x$ 里面一块填充字符，其方案数就是 $\sum_c P_k^{c+w} f_{m-2w,c}$。

还有一个地方没处理，我们怎么计算没有 $\operatorname{border}$ 的 $T$ 的方案数？直接拿所有的 $T$ 方案数减去所有有 $\operatorname{border}$ 的即可。

最后只要预处理 $k$ 的次幂和 $P_k^i$ （其中 $i\leq 2m$）就行了！比那些式子又臭又长的好到不知道哪里去了！！1

Code

代码有注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int N=1e6+10,M=4e3+10,INF=0x3f3f3f3f3f3f3f3f,mod=1000000007;
int n,m,k;
int f[M][M];
int Pk[M],pk[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	
	//使用 Straightforward DP 预处理 f
	f[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=min(i,k);j++){
			f[i][j]=f[i-1][j-1];
			if(i>=2)f[i][j]=(f[i][j]+f[i-2][j-1]*(i-1)%mod)%mod;
		}
	}
	
	//预处理k选i进行排列的方案数，要预处理到 2M
	Pk[0]=1;
	for(int i=1;i<M;i++)Pk[i]=Pk[i-1]*(k-i+1)%mod;
	
	//预处理k的次幂（注意要处理到 N）
	pk[0]=1;
	for(int i=1;i<N;i++)pk[i]=pk[i-1]*k%mod;
	
	//计算所有的T方案数
	int sum=0,ans=0;
	for(int c=1;c<=m;c++)sum=(sum+f[m][c]*Pk[c]%mod)%mod;
	
	for(int w=1;w*2<=m;w++){//枚举w长度
		int x=m-w*2,tmp=0;
		
		//枚举字符数c，计算方案数
		for(int c=0;c<=x&&w+c<=k;c++)tmp=(tmp+f[x][c]*Pk[c+w])%mod;
		
		//从总数里减去有border的方案数
		sum=((sum-tmp)%mod+mod)%mod;
		
		//进行一个容的斥，计算贡献
		int co=1,len=m;
		while(len<=n){
			ans=((ans+co*pk[n-len]*tmp%mod*(n-len+1)%mod)%mod+mod)%mod;
			co*=-1;
			len+=x+w;
		}
	}
	
	//计算没有border的T的贡献
	ans=(ans+sum*pk[n-m]%mod*(n-m+1)%mod)%mod;
	
	cout<<ans<<endl;
	return 0;
}