好妙的题啊
首先容易想到简单容斥，统计合法方案数可以考虑总方案数减去不合法方案数
那么先考虑如何判断一个串是否合法，但是直接判断好像很不好搞
这时候就需要一些 $magic$ 了，把所有位置下标为奇数的字符 $ ext{A}$ 换成 $ ext{B}$ ，$ ext{B}$ 换成 $ ext{A}$
然后发现对于转化后的串，原本的限制变成了不能删除 $AA$ 和 $BB$ ，考虑到原串和新串是一一对应的
所以如果能算出合法新串的数量那么即为答案
然后容易发现，新串合法的充分必要条件为：字符 $A$ 和字符 $B$ 数量的最大值不超过 $n/2$
首先显然是必要的，因为如果某一个字符 $c$ 数量超过一半其他的字符不管怎么和 $c$ 抵消最后都会剩下一些 $c$ 没法消除
然后也容易证明是充分的，对于任意时刻，假设此时 $A$ 的数量大于等于 $B$ 的数量，那么我们只要优先让 $A$ 和其他字符抵消
显然一定存在某个 $A$ 它的旁边有其他字符
如果 $B$ 的数量比 $A$ 多，我们也只要优先消 $B$ 即可
那么证明完成了，统计不合法方案十分简单，枚举 $k>n/2$ ，然后算一下 $n$ 个位置任意选 $k$ 个填 $A$ ，剩下其他位置填不为 $A$ 的字符的方案数
$B$ 也同理，然后就做完了
这里简单容斥的时候显然不用再加上 $A,B$ 数量同时大于 $n/2$ 的情况（因为不存在）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e7+7,mo=998244353; inline int fk(int x) { return x>=mo ? x-mo : x; } int n,fac[N],facinv[N]; int ksm(int x,int y) { int res=1; while(y) { if(y&1) res=1ll*res*x%mo; x=1ll*x*x%mo; y>>=1; } return res; } inline int C(int x,int y) { return 1ll*fac[x]*facinv[y]%mo*facinv[x-y]%mo; } int main() { n=read(); fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mo; facinv[n]=ksm(fac[n],mo-2); for(int i=n-1;i>=0;i--) facinv[i]=1ll*facinv[i+1]*(i+1)%mo; int ans=ksm(3,n); for(int k=n/2+1;k<=n;k++) ans=fk(ans-2ll*C(n,k)*ksm(2,n-k)%mo+mo); printf("%d ",ans); return 0; }