CF1227F1 Wrong Answer on test 233 (Easy Version)

点这通往Hard版题解/)

Easy版是个dp题

题解：

$f[i][j]$表示前$i$道题，$s2$比$s1$多对$j$道题（注意$j$值域$[-n,n]$，所以代码中要额外加个$n$）

初始化$f[0][0]=1$

转移有两种

假设第$i$题答案为$A$，$i$后面一题答案为$B$

• 若$A==B$，则$f[i][j]=f[i-1][j]*k$，意思是无论第i题怎样选，s1和s2的差
  都不会因此而改变，要么都对，要么都错

• 若$A!=B$，则$f[i][j]=f[i-1][j-1]+f[i-1][j+1]+(k-2)*f[i-1][j]$，意
  思是一种自己错的方法，一种自己对的方法，k-2种都错的方法

最后答案就是$\sum\limits_{i=1}^{n}f[n][i]$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=998244353;
const int N=2005;
int n,k,ans,a[N],b[N],f[N][N<<1];

signed main(){
    read(n);read(k);
    for(int i=1;i<=n;i++) read(a[i]),b[i%n+1]=a[i]; //b[]是移位后的a[]
    if(k==1){
        write(0);
        return 0;
    }
    f[0][0+n]=1;
    for(int i=1;i<=n;i++){
        if(a[i]==b[i]){
            for(int j=-n;j<=n;j++)
                f[i][j+n]=f[i-1][j+n]*k%mod;
        }
        else{
            for(int j=-n;j<=n;j++)
                f[i][j+n]=(f[i-1][j-1+n]+f[i-1][j+1+n]+(k-2)*f[i-1][j+n])%mod;
        }
    }
    for(int i=1;i<=n;i++)
        (ans+=f[n][i+n])%=mod;
    write(ans);
}