·Choose two consecutive characters in s and erase them. However, choosing ‘AB‘ or ‘BA‘ is not allowed.For example, ‘ABBC‘ satisfies the condition for N=4, because we can convert it as follows: ‘ABBC‘ → (erase ‘B‘B) → ‘AC‘ → (erase ‘AC‘) → ‘(empty)‘.
2
7
思路：首先不考虑‘C‘。把奇数位‘A‘ ‘B‘互换，问题等价转换为只能消除相异的相邻两个字符，最终能消完的串有多少个。
这个问题的答案是‘A‘ ‘B‘字符数相同的（即都等于n/2）串的个数。
那么考虑‘C‘的话，‘C‘可以被看做是‘A‘ ‘B‘里任意一个，所以只要满足‘A‘ ‘B‘字符个数的差不超过‘C‘的个数，那么这个串就能被消完。
所以不能被消完的串 就是num[‘A‘]>n/2 或 num[‘B‘]>n/2 的串。枚举统计有多少。
最后答案是总个数-不能被消完的个数。
#include<bits/stdc++.h> #pragma GCC optimize(2) typedef long long ll; using namespace std; const ll mod=998244353; ll f[10000005],invf[10000005]; inline ll qpow(ll a,ll b){ ll ret=1; while(b){ if(b&1) ret=ret*a%mod; a=a*a%mod; b>>=1; } return ret; } inline void init(ll n){ f[0]=1; for(ll i=1;i<=n;i++) f[i]=f[i-1]*i%mod; invf[n]=qpow(f[n],mod-2); for(ll i=n-1;i>=0;i--) invf[i]=invf[i+1]*(i+1)%mod; } inline ll C(ll n,ll m){ if(m<0||m>n) return 0; if(m==0||m==n) return 1; return f[n]*invf[m]%mod*invf[n-m]%mod; } int main() { ll n;scanf("%lld",&n); init(n); ll ans=0; for(ll i=n/2+1;i<=n;i++){ ans=(ans+C(n,i)*qpow(2,n-i))%mod; } ans=(qpow(3,n)-2*ans%mod+mod)%mod; printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/lllxq/p/12193190.html
