给定正整数 \(n,k\) 和长为 \(m\) 的正整数序列 \(A\)。
定义一个序列是好的当且仅当存在其一个子串是 \([k]\) 的排列。
求所有长为 \(n\) 的好序列中 \(A\) 的出现次数之和\(\bmod(10^9+7)\)。
\(m,n\le 25000,k\le 400\)。
考虑反面情况，用总方案数 \(k^{n-m}(n-m+1)\) 减去坏序列包含 \(A\) 的次数之和，分情况讨论：
若 \(A\) 是好的，则显然答案为 \(0\)。
若 \(A\) 中没有两个元素相同，则此时的答案只与 \(m\) 有关，所求即为坏序列中长为 \(m\) 的值互不相同的子段个数之和\(/k^{m\downarrow}\)。
这个可以直接 dp，设 \(f_{i,j,0/1}\) 表示当前做到序列第 \(i\) 位，最长的值互不相同的后缀长度为 \(j\)，是否选择了 \(A\) 所在位置。时间复杂度 \(O(nk)\)。
若 \(A\) 中有两个元素相同，则 \(A\) 的两边独立。答案只与 \(A\) 的最长的值互不相同的前/后缀长度 \(pre,suf\) 有关，两边分别做一遍 dp，然后枚举 \(A\) 的位置，用乘法原理乘起来再求和即可，时间复杂度 \(O(nk)\)。然后就...做完了？
大家都说这事 sb 题，可事实上有这么 sb 么？好像确实
这个 dp 也可以换一种好的理解方式。先设计一个状态 \(i\) 表示最长的值互不相同的后缀长度为 \(i\)。
不考虑具体的字符，只考虑字符之间的相等关系，这个 dp 是一个 DFA 上路径计数的形式。
这个 DFA 有 \(k+1\) 个点，每个点有 \(k\) 条出边。\(i\) 这个点有 \(k-i\) 条边连向 \(i+1\)，分别有一条边连向 \(1,2,3,\cdots,i\)。
选择一个长为 \(m\) 的子段可以看做建分层图的扩展，走到一个编号 \(\ge m\) 的点时可以选择从第 \(0\) 层走到第 \(1\) 层，也可以选择在同层之间走。
至于上面的第三种情况，设 \(A\) 前面长度为 \(a\)，后面长度为 \(b\)，则前缀的方案数即为从 \(pre\) 这个点开始走 \(a\) 步的方案数，后缀同理。
这大概也就是 DFA 上 dp 的一般思路了吧，可能看上去清晰一点。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 25003, M = 403, mod = 1e9 + 7;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0; bool f = false;
for(;ch < ‘0‘ || ch > ‘9‘;ch = getchar()) f |= ch == ‘-‘;
for(;ch >= ‘0‘ && ch <= ‘9‘;ch = getchar()) x = x * 10 + ch - ‘0‘;
if(f) x = -x;
} int ksm(int a, int b){
int res = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) res = (LL)res * a % mod;
return res;
} int n, k, m, A[N], ans, pre, suf, buc[N]; bool vis[M];
bool check(){
int cnt = 0;
for(int i = 1;i <= m;++ i){
cnt += !buc[A[i]]++;
if(cnt == k) return true;
if(i > k) cnt -= !--buc[A[i-k]];
} return false;
} void qmo(int &x){x += x >> 31 & mod;}
int f[2][2][M], dp[2][M], tmp1[N], tmp2[N];
int main(){
read(n); read(k); read(m);
for(int i = 1;i <= m;++ i) read(A[i]);
ans = (n-m+1ll) * ksm(k, n-m) % mod;
if(check()){printf("%d\n", ans); return 0;}
memset(vis, 0, sizeof vis);
pre = suf = m;
for(int i = 1;i <= m;++ i){
if(vis[A[i]]){pre = i-1; break;}
vis[A[i]] = true;
} memset(vis, 0, sizeof vis);
for(int i = m;i;-- i){
if(vis[A[i]]){suf = m-i; break;}
vis[A[i]] = true;
} if(pre == m){
int cur = 0; f[0][0][1] = k;
if(m == 1) f[0][1][1] = k;
for(int i = 2;i <= n;++ i, cur ^= 1){
memset(f[!cur], 0, sizeof f[!cur]);
for(int j = k-1, tmp1 = 0, tmp2 = 0;j;-- j){
qmo(tmp1 += f[cur][0][j] - mod);
qmo(tmp2 += f[cur][1][j] - mod);
f[!cur][0][j] = ((k-j+1ll) * f[cur][0][j-1] + tmp1) % mod;
f[!cur][1][j] = ((k-j+1ll) * f[cur][1][j-1] + tmp2) % mod;
if(j >= m) qmo(f[!cur][1][j] += f[!cur][0][j] - mod);
}
} int res = 0, tmp = 1;
for(int i = 1;i < k;++ i) qmo(res += f[cur][1][i] - mod);
for(int i = k;i > k-m;-- i) tmp = (LL)tmp * i % mod;
qmo(ans -= (LL)res * ksm(tmp, mod-2) % mod);
} else { dp[0][pre] = tmp1[0] = tmp2[0] = 1;
for(int i = 1, cur = 0;i <= n-m;++ i, cur ^= 1){
memset(dp[!cur], 0, sizeof dp[!cur]);
for(int j = k-1, tmp = 0;j;-- j){
qmo(tmp += dp[cur][j] - mod);
dp[!cur][j] = ((k-j+1ll) * dp[cur][j-1] + tmp) % mod;
qmo(tmp1[i] += dp[!cur][j] - mod);
}
} memset(dp[0], 0, sizeof dp[0]); dp[0][suf] = 1;
for(int i = 1, cur = 0;i <= n-m;++ i, cur ^= 1){
memset(dp[!cur], 0, sizeof dp[!cur]);
for(int j = k-1, tmp = 0;j;-- j){
qmo(tmp += dp[cur][j] - mod);
dp[!cur][j] = ((k-j+1ll) * dp[cur][j-1] + tmp) % mod;
qmo(tmp2[i] += dp[!cur][j] - mod);
}
} for(int i = 0;i <= n-m;++ i) qmo(ans -= (LL)tmp1[i] * tmp2[n-m-i] % mod);
} printf("%d\n", ans);
}
坑：判断好序列需要开一个桶记录当前窗口中每个数的出现次数，不能只用一个 bool 数组就解决。
原文：https://www.cnblogs.com/AThousandMoons/p/14551679.html