题意
定义一个长度为 \(n\) 的序列为 k 好序列当且仅当该序列存在一个长度为 \(k\) 的连续子序列构成 \(1\sim k\) 的排列。
定义一个 k 好序列的权值为特殊序列序列 \(\{b_i\}\) 在该序列中的出现次数。
序列值域为 \([1,k]\)，求所有 k 好序列的权值之和。
\(n\le 2.5\times10^4,k\le 400\)
分析
原问题做起来有点棘手，不妨考虑正难则反，将原问题转化为求 所有序列的权值 减去 非 k 好序列的权值。拆贡献易得前半部分答案为 \((n-m+1)\cdot k^{n-m}\)，现在只需要求后半部分就行了。
分类讨论一下：
1. 特殊序列本身存在 k 好序列
此时后半部分答案为 0。
2. 特殊序列存在重复出现的元素
由于有重复元素，所以不可能存在长为 \(k\) 的排列横跨特殊序列，这样序列两端的情况就相互独立了，只需要保证两端都没有长为 \(k\) 的排列即可。设 \(f_{i,j}\) 表示左侧扩展了 \(i\) 位，极长无重复元素的序列长为 \(j\) 的方案数。\(g_{i,j}\) 表示右侧。转移考虑新接一个未出现的数，\(f_{i+1,j+1}\leftarrow f_{i,j}\cdot (k-j)\)，或者接一个已经出现的数，\(f_{i+1,p}\leftarrow f_{i,j},p\le j\)。该 DP 可以用后缀和优化做到 \(O(nk)\)。
然后枚举一下左侧扩展多少即可。合并是一个卷积形式。
3. 特殊序列不存在重复元素
若继续按照上述思路做复杂度会退化到 \(O(nk^2)\)，考虑一个新的做法，我们考虑计算所有非 k 好序列的“m 好序列”连续子序列数量之和，由于不同的颜色地位相同，所以在这些 m 好序列上出现特殊序列与出现其他序列的情况数是相等的，最终把求出来的答案除以 \(A_{k-1}^{m-1}\)（因为 DP 数组定义中最后一个位置的颜色没有被钦定，我们只需要钦定最后一个位置为特殊序列最后一位即可，故不需要除以 \(A_k^m\)）。
所有非 k 好序列的“m 好序列”连续子序列数量之和也可以通过情况 2 的类似 DP 来求解，区别在于要记两个 DP 数组分别表示方案数和 m 好序列数，转移也要比情况 2 多一条。同样需要后缀和优化，时间复杂度 \(O(nk)\)。
综上，时间复杂度 \(O(nk)\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define IOS ios::sync_with_stdio(false)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define popc __builtin_popcountll
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
template<typename T>
inline void write(T x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=2.5e4+5,maxk=405,inf=0x3f3f3f3f,mod=1e9+7;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,k,m,ans;
int a[maxn];
int ksm(int x,int y){
int res=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod;
return res;
}
inline void add(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
bool vis[maxn];
bool ck(){
rep(s,1,m-k+1){
rep(i,1,k)vis[i]=0;
bool ok=1;
rep(i,0,k-1){
if(vis[a[s+i]]){ok=0;break;}
vis[a[s+i]]=1;
}
if(ok)return 1;
}
return 0;
}
int sf[maxk],sg[maxk];
int f[maxn][maxk],g[maxn][maxk];
bool visf[maxk],visg[maxk];
void solve1(int Fx,int Gx){
f[0][Fx]=g[0][Gx]=1;
rep(i,1,Fx)sf[i]=1;
rep(i,1,Gx)sg[i]=1;
rep(i,1,n){
rep(j,1,k-1){
f[i][j]=1ll*f[i-1][j-1]*(k-j+1)%mod;
add(f[i][j],sf[j]);
g[i][j]=1ll*g[i-1][j-1]*(k-j+1)%mod;
add(g[i][j],sg[j]);
}
sf[k]=sg[k]=0;
per(j,k-1,1)sf[j]=(sf[j+1]+f[i][j])%mod,sg[j]=(sg[j+1]+g[i][j])%mod;
}
int res=0;
rep(i,0,n-m){
int sumf=0,sumg=0;
rep(j,1,k-1)add(sumf,f[i][j]),add(sumg,g[n-m-i][j]);
add(res,1ll*sumf*sumg%mod);
}
write((ans+mod-res)%mod);
}
int fac[maxn],inv[maxn];
int A(int x,int y){
if(x<y)return 0;
return 1ll*fac[x]*inv[x-y]%mod;
}
void solve2(){
fac[0]=1;rep(i,1,k)fac[i]=1ll*fac[i-1]*i%mod;
inv[k]=ksm(fac[k],mod-2);per(i,k-1,0)inv[i]=1ll*inv[i+1]*(i+1)%mod;
f[1][1]=sf[1]=1;
if(m==1)g[1][1]=sg[1]=1;
rep(i,2,n){
rep(j,1,k-1){
f[i][j]=1ll*f[i-1][j-1]*(k-j+1)%mod;
add(f[i][j],sf[j]);
g[i][j]=1ll*g[i-1][j-1]*(k-j+1)%mod;
add(g[i][j],sg[j]);
}
sf[k]=sg[k]=0;
per(j,k-1,1)sf[j]=(sf[j+1]+f[i][j])%mod;
rep(j,m,k-1)add(g[i][j],f[i][j]);
per(j,k-1,1)sg[j]=(sg[j+1]+g[i][j])%mod;
}
// write(sg[1],32);
int res=1ll*sg[1]*ksm(A(k-1,m-1),mod-2)%mod;
write((ans-res+mod)%mod);
}
inline void solve_the_problem(){
n=rd(),k=rd(),m=rd();
rep(i,1,m)a[i]=rd();
ans=1ll*(n-m+1)*ksm(k,n-m)%mod;
if(ck())return write(ans);
int fst=-1,lst=-1;
rep(i,1,m){
if(visf[a[i]]){fst=i-1;break;}
visf[a[i]]=1;
}
per(i,m,1){
if(visg[a[i]]){lst=m-i;break;}
visg[a[i]]=1;
}
if(fst==-1&&lst==-1)return solve2();
return solve1(fst,lst);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;
while(_--)solve_the_problem();
}
/*
*/