简要题意
一个长度为 \(n\) 的元素在 \([1,k]\) 的整数序列 \(a\) 的价值定义如下。
- 初始 \(i=1\)，如果 \(a_{i\sim i+k-1}\) 包含了 \(1 \sim k\) 的所有整数，则价值加 \(1\)，然后令 \(i=i+k\)。如果没有包含 \(1\sim k\) 的所有整数则 \(i=i+1\)，直到 \(i \geq n-k+2\) 时结束。
对于给定的 \(k\)，求所有长度为 \(n\) 的序列的价值和。
做法
我们称一个位置 \(x\) 是匹配的，当且仅当在序列中选出的段中包含 \([x-k+1,x]\)。
考虑设计 dp。
设 \(f_i\) 表示长度为 \(i\) 的序列，只存在一个匹配位置，且这个位置为 \(i\) 的方案数。
设 \(F_i\) 表示长度为 \(i\) 的序列，不存在匹配位置的方案数。
设 \(g_i\) 表示长度为 \(i\) 的序列，有一个匹配位置为 \(i\) 的方案数。
设 \(dp_i\) 表示长度为 \(i\) 的序列，有一个匹配位置为 \(i\) 的所有序列的价值和。
不难发现最后的答案就是 \(\sum F_{n-i}dp_i\)。
转移如下。
\[f_i=k!k^{i-k}-\sum_{j=k}^{i-1} f_j k^{\max\{0,i-k-j\}}(\min\{k,i-j\})! \]考虑用总方案数减去不合法的方案乘上系数就可以得到上述式子。
\[F_i=k^i-\sum_{j=1}^i f_j k^{i-j} \]依然是考虑用总方案数减去不合法方案数。
\[g_i=\sum_{j=0}^{i-k} g_jf_{i-j} \]\[dp_i=\sum_{j=0}^{i-k} (g_j+dp_j)f_{i-j} \]然后就可以在 \(O(n^2)\) 时间内求出答案了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 4004;
const int mod = 998244353;
int n, k, res, p[MAXN];
int f[MAXN], fac[MAXN], ifac[MAXN], dp[MAXN], g[MAXN], F[MAXN];
ll powc[MAXN];
int main(){
cin >> n >> k; powc[0]=1; fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=n;++i) powc[i]=powc[i-1]*k%mod;
ll p=1; for(int i=1;i<=k;++i) p=p*i%mod; f[k]=p;
for(int i=0;i<k;++i) F[i]=powc[i]; F[k]=(powc[k]-f[k]+mod)%mod;
for(int i=k+1;i<=n;++i){
f[i]=p*powc[i-k]%mod; int t=i-k+1;
for(int j=k;j<i;++j){
if(t<=j) (f[i]-=1ll*f[j]*fac[k-(j-t+1)]%mod-mod)%=mod;
else (f[i]-=1ll*f[j]*powc[t-j-1]%mod*p%mod-mod)%=mod;
}
F[i]=powc[i];
for(int j=1;j<=i;++j) (F[i]-=1ll*f[j]*powc[i-j]%mod-mod)%=mod;
}
dp[0]=0, g[0]=1; ll sum=0;
for(int i=k;i<=n;++i){
for(int j=i-k;j>=0;--j){
(g[i]+=1ll*g[j]*f[i-j]%mod)%=mod;
(dp[i]+=1ll*(g[j]+dp[j])*f[i-j]%mod)%=mod;
}
sum+=1ll*dp[i]*F[n-i]%mod; sum%=mod;
}
cout << sum;
return 0;
}