题目
解法
做法有两种, O ( n 2 ) 或 O ( n k ) O(n^2)或O(nk) O(n2)或O(nk)
主要是第二种做法
设计状态:
f i , j : 前 i 个数,后缀不重集的长度为 j 的方案数 f_{i,j}:前i个数,后缀不重集的长度为j的方案数 fi,j:前i个数,后缀不重集的长度为j的方案数
a n s = ∑ i f i , 0 ∗ k n − i ans=\sum_i f_{i,0}*k^{n-i} ans=∑ifi,0∗kn−i
注意一下状态转移不要算重即可
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N=4e3+7,mod=998244353;
int n,m;
ll ans;
ll f[N][N],t[N];
ll add(ll x,ll y) { return (x+y)%mod; }
ll del(ll x,ll y) { return ((x-y<0)?x-y+mod:x-y); }
ll mul(ll x,ll y) { return (x*y%mod); }
int main() {scanf("%d%d",&n,&m);t[0]=1; for(int i=1;i<=n;i++) t[i]=t[i-1]*m%mod;f[0][0]=1;for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(j==m-1) f[i+1][0]=add(f[i+1][0],mul(f[i][j],m-j)),f[i+1][1]=del(f[i+1][1],mul(f[i][j],m-j));else f[i+1][j+1]=add(f[i+1][j+1],mul(f[i][j],m-j)),f[i+1][j+2]=del(f[i+1][j+2],mul(f[i][j],m-j));if(i==0 && j==0) continue;f[i+1][1]=add(f[i+1][1],f[i][j]),f[i+1][j+1]=del(f[i+1][j+1],f[i][j]);}for(int j=1;j<m;j++) f[i+1][j]=add(f[i+1][j],f[i+1][j-1]);ans=add(ans,mul(f[i+1][0],t[n-i-1]));}printf("%lld\n",ans);
}