CF1227F2 Wrong Answer on test 233 (Hard Version)

点这通往Easy版题解/)

Hard版是个组合数学题，但只要发现了对称性比Easy更简单。。。

题解：

假设你已经通过各种奇奇怪怪的方法发现了Easy版中，$f[i][j]=f[i][-j]$这一性质（比方说大眼观察这对称的dp方程啊（雾）），可以得到如下推导

已知$ANS=\sum\limits_{i=1}^{n}f[i][j] [j>0]$，$\sum\limits_{i=1}^{n}f[i][j] [j>0]=\sum\limits_{i=1}^{n}f[i][j] [j<0]$，总方案数=$k^n$

可得$ANS=\frac{k^n-\sum\limits_{i=1}^{n}f[i][0]}{2}$

也就是我们现在要求出变化前后分数相同的方案数

设$m=\sum\limits_{i=1}^{n}[a_i==a_{nxt(i)}]$

与Easy同理，容易发现只有这m题会引起分数差的改变

我们可以从0到$\left \lfloor \frac{m}{2} \right \rfloor$枚举$i$表示这m题中有i道导致分数差-1，同时这需要i道导致分数差+1的题来抵消影响

选择这$2i$道题的方案数就是$\binom{m}{i}\binom{m-i}{i}$，同时还要乘上$(k-2)^{m-2*i}$，因为剩下的题想不造成影响，各自都有k-2种选择

$i$枚举累加完后，还要再乘上一个$k^{n-m}$，因为那些题无论怎么选都不会造成影响

所以最后可以得到：

依式计算即可

代码：

#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=2e5+5;
int n,k,f[N],inv[N],ans,a[N],b[N],m;

int fpow(int x,int y,int mod){
    int res=1;
    for(;y;y>>=1,mod?(x*=x)%=mod:x*=x) if(y&1) mod?(res*=x)%=mod:res*=x;
    return res;
}

int C(int n,int m){
    return f[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
    read(n);read(k);
    for(int i=1;i<=n;i++) read(a[i]),b[i%n+1]=a[i];
    if(k==1){
        write(0);
        return 0;
    }
    for(int i=1;i<=n;i++) if(a[i]^b[i]) m++;

    f[0]=1;
    for(int i=1;i<=m;i++) f[i]=f[i-1]*i%mod;
    inv[m]=fpow(f[m],mod-2,mod);
    for(int i=m-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

    for(int i=0;i*2<=m;i++)
        (ans+=C(m,i)*C(m-i,i)%mod*fpow(k-2,m-i*2,mod)%mod)%=mod;
    (ans*=fpow(k,n-m,mod))%=mod;

    write((fpow(k,n,mod)-ans+mod)%mod*fpow(2,mod-2,mod)%mod);
}
赏

fighter