- 给定(n,k)和一个长为(m)的值在([1,k])范围内的序列(a)。
- 定义一个序列是好的，当且仅当它长度为(n)、所有值在([1,k])范围内且存在一个长度为(k)的子串是(1sim k)的一个排列。
- 求所有好序列中(a)的出现次数之和。
- (mle nle2.5 imes10^4,kle400)
容斥
发现存在一个长度为(k)的排列的限制有点烦人，因此我们容斥，用总方案数减去非法方案数。
长度已知为(n)，求的又是出现次数之和，我们可以分别考虑(a)以每个位置为开头的贡献，而其余位置都可以任填，因此就是((n-m+1) imes k^{n-m})。
非法方案数就需要大力分类讨论。
(a)中包含(1sim k)的排列
直接在(a)中暴枚起点向后枚举(k)位即可判断是否存在一个排列。
如果存在，显然含(a)的序列都是合法的，也就是说非法方案数为(0)，直接输出总方案数即可。
(a)中包含重复的元素
也就是说不可能存在一个排列包含(a)，因此我们可以分别考虑(a)的左右两端。
设(f_{i,j})表示一个长度为(i)的非法序列，后缀极长排列长度为(j)的方案数。
转移就考虑填入一个不在排列中的数使排列长度加(1)，或填入排列中的一个数，可以使新的排列变成(1sim j)中的任意一种长度。
因此得出转移方程：
后面的(sum)只要我们从大到小枚举(j)同时维护(f_{i-1,j})的后缀和即可优化转移。
然后我们假设(a)的前缀极长排列长度为(x)，后缀极长排列长度为(y)。
并上前后部分，交界处的极长排列长度分别可以是([x,k))和([y,k))中的一个数。
因此在(a)前面放一个长度为(i)的序列使得拼成序列仍然非法的方案数为：（因为最后长为(x)的排列填数已知，要除以一个排列数）
不妨令(s1_i=sum_{j=x}^{k-1}f_{i,j})，同理设(s2_i=sum_{j=y}^{k-1}f_{i,j})。
然后只要按照先前提到过的方法，枚举(a)的开头位置，则前后要放的序列长度都已知，直接利用(s1)和(s2)两个数组计算即可。
最后给答案除以(A_k^x imes A_k^y)。
(a)中不含重复的元素
此时的(a)相当于是一个长度为(m)的排列。
则我们直接求出所有长度为(m)的排列的贡献，然后只要给它除以一个(A_k^m)即可。
仿照(f_{i,j})，设(g_{i,j})表示一个长度为(i)的非法序列，后缀极长排列长度为(j)的所有方案下，长度为(m)的排列出现次数之和。
转移方程也是类似的，只是要考虑上在这个位置添上排列的方案数，即：
那么非法方案数就应该是(frac{sum_{j=1}^{k-1}g_{n,j}}{A_k^m})。
代码：(O(nk))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 25000
#define K 400
#define X 1000000007
using namespace std;
int n,m,k,a[N+5],p[K+5],Fac[N+5],IFac[N+5],s1[N+5],s2[N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int f[N+5][K+5];I void DP_f()//动态规划求解f数组
{
f[1][1]=k;for(RI i=2;i<=n;++i) for(RI j=k-1,t=0;j;--j)
t=(t+f[i-1][j])%X,f[i][j]=(1LL*f[i-1][j-1]*(k-(j-1))+t)%X;
}
int g[N+5][K+5];I void DP_g()//动态规划求解g数组
{
g[1][1]=k*(m==1);for(RI i=2;i<=n;++i) for(RI j=k-1,t=0;j;--j)
t=(t+g[i-1][j])%X,g[i][j]=(1LL*g[i-1][j-1]*(k-(j-1))+t)%X,j>=m&&(g[i][j]=(g[i][j]+f[i][j])%X);//算上这个位置添上排列的方案数
}
int main()
{
RI i,j,tg=1;for(read(n,k,m),i=1;i<=m;++i) read(a[i]),p[a[i]]?tg=0:p[a[i]]=1;
for(Fac[0]=IFac[0]=i=1;i<=max(m,k);++i) Fac[i]=1LL*Fac[i-1]*i%X,IFac[i]=QP(Fac[i],X-2);
RI o=1LL*(n-m+1)*QP(k,n-m)%X,t=0;for(i=1;i+k-1<=m;++i)//枚举长度为k排列的起始位置
{for(j=1;j<=k&&p[a[i+j-1]]^(-i);++j) p[a[i+j-1]]=-i;if(j>k) return printf("%d
",o),0;}//如果存在，直接输出总方案数
#define IA(x) (1LL*IFac[k]*Fac[k-(x)]%X)//A(k,x)的逆元
if(DP_f(),tg) {for(DP_g(),i=1;i^k;++i) t=(t+g[n][i])%X;return printf("%d
",(o-1LL*t*IA(m)%X+X)%X),0;}//如果本身是排列，DP出g计算
RI x;for(x=1;p[a[x]]^2;++x) p[a[x]]=2;for(x=x-1,i=1;i<=n;++i) for(j=x;j^k;++j) s1[i]=(s1[i]+f[i][j])%X;//前缀最长排列x
RI y;for(y=m;p[a[y]]^3;--y) p[a[y]]=3;for(y=m-y,i=1;i<=n;++i) for(j=y;j^k;++j) s2[i]=(s2[i]+f[i][j])%X;//后缀最长排列y
for(i=0,j=n-m;~j;++i,--j) t=(1LL*s1[i+x]*s2[j+y]+t)%X;return printf("%d
",(o-1LL*t*IA(x)%X*IA(y)%X+X)%X),0;//枚举A的起始位置计算方案数
}