简要题意

给定 \(n\)，\(k\) 和值域 \([1,k]\) 的 \(n\) 个整数 \(h_i\)，求有多少个长为 \(n\) 的整数序列 \(a\) 满足值域 \([1,k]\)，且 \(\sum\limits_{i=1}^n[a_i=h_i]<\sum\limits_{i=1}^n[a_i=h_{(i\bmod{n})+1}]\)。答案对 \(998244353\) 取模。

\(1 \leq n \leq 2\times 10^3,1 \leq k \leq 10^9\)

思路

小清新二维 DP 题。

令 \(f_{i,j}\) 为截止到第 \(i\) 位，比原来的少错 \(j\) 个数的方案数。

则动态转移方程为：

方程解释：

• 对于第一种情况，由于变换后对结果没有影响，所以只能从 \(f_{i-1,j}\) 转移而来， 乘上值域。
• 对于第二种情况 \(f_{i-1,j-1}\) 是多对了一题，\(f_{i-1,j+1}\) 是少对了一题。这两种情况占了 \(2\) 个值，所以剩下的没变的 \(f_{i-1,j}\) 就只有 \(k-2\) 种了。

我们要求的是比原来多的方案数，就是 \(\sum_{i=1}^{n}{f_{n,i}}\)。

边界：\(f_{0,0}=1\)。

时间复杂度 \(O(n^2)\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4000+5;
const int mod = 998244353;

int F[N][N];
int n,k,h[N];

int& f(int i,int j){
    return F[i][j+n];
}
int M(const int &x){
    return (x%mod+mod)%mod;
}

signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    f(0,0)=1;
    for(int i=1;i<=n;i++){
        for(int j=-n;j<=n;j++){
            if(h[i]==h[i%n+1]){
                f(i,j)=M(f(i-1,j)*k);
            }
            else{
                f(i,j)=M(M(f(i-1,j-1)+f(i-1,j+1))+M(f(i-1,j)*((k-2))));
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=f(n,i);
        ans=M(ans);
    }
    cout<<ans;
    return 0;
}