【AtCoder - agc040_c】Neither AB nor BA 想法+組合數學

題意

求長度為n（n為偶數）的滿足以下條件的字元串數量。

• 字元串中隻含有ABC三種字母，且字元串的長度為偶數。
• 字元串可以按照以下規則删除成空串
  • 相鄰兩個字母隻要不是AB或者BA都可以删除

題解

因為容易發現奇數位上的A與偶數位上的B不能消去，奇數位上的B與偶數位上的A也是同理

是以做一個巧妙的轉化，把所有奇數位上的A換成B，所有奇數位上的B換成A

例如，ABCBBABBAC轉化BBCBAAABBC

這樣轉換之後就會發現，原來的規則是AB和BA不能消除，現在變成了AA不能消除，BB不能消除

這樣就容易發現，想要消除一個A必須跟一個B或者一個C一起消除，B也是同理。

那麼在這樣的情況下：

• 如果A的數量超過字元串長度的一半，那麼勢必無法全部消除
• 如果B的數量超過字元串長度的一半，那麼勢必也無法全部消除

那麼要求能全部删除的數量，隻需要用總數 - 不能完全删除的數量即可得答案

不能完全删除的數量可以這樣計算，根據上面的條件可知，隻要讓A或者B的數量大于字元串長度的一半即可

一個小Tip：可能有同學會覺得，A的數量大于一半就不能消除不是經過轉化之後得出的結論嗎？那我們要算不能完全删除的數量不是應該轉化回去計算嗎？（對！沒錯這個“有同學”就是我）

其實細品一下會發現，就按照轉化之後的結論計算完全沒問題，因為要構造不合法的情況，你就按照我們的結論，放上大于n/2個A，然後再把奇數位上的A和B按照之前轉化過來的規則轉化回去，就是本題真正要求的不合法的情況。正因為我們轉化前後兩種情況是等價的，是以構造出來的不合法的情況，經過轉化之後也是等價的。

又因為轉化回去構造的話考慮起來蠻複雜的，什麼奇A偶B，奇B偶A，是以不如就在轉化之後這裡計算不合法的數量友善，是以幹脆就直接按照轉化之後的結論構造即可得出答案（因為我們清楚這兩者是等價的啦）

那麼隻需要處理出A不合法的情況數，再 * 2就是A和B總共的不合法情況數量。

也就是枚舉A的數量t從n/2+1到n，給A從n個位置中挑出t個位置

剩下的位置，每個位置都有兩種選擇B或者C，那麼A不合法的情況數就是 C ( n , t ) ∗ 2 n − t C(n,t)*2^{n-t} C(n,t)∗2n−t

長度為n的字元串，每個位置有ABC三種選擇，是以字元串總數為 3 n 3^n 3n

長度為n的合法的字元串數量 = 字元串總數 - 不合法字元串數量 = 3 n − 2 ∗ C ( n , t ) ∗ 2 n − t 3^n-2*C(n,t)*2^{n-t} 3n−2∗C(n,t)∗2n−t

/****************************
* Author : W.A.R            *
* Date : 2020-10-08-20:19   *
****************************/
/*
https://vjudge.net/problem/AtCoder-agc040_c
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define show(x) std:: cerr << #x << " = " << x << std::endl;
#define mem(a,x) memset(a,x,sizeof(a))
#define Rint register int
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const int maxm=2e6+10;
const ll mod=998244353;

ll fac[maxn],invFac[maxn],mi[maxn],n,sum;
ll qpow(ll a,ll n){
	a%=mod;
	ll ans=1;
	while(n){
		if(n%2)ans=ans*a%mod;
		n/=2;
		a=a*a%mod;
	}
	return ans;
}
ll C(ll n,ll m){
	if(m>n||m<0)return 0;
	return fac[n]*invFac[n-m]%mod*invFac[m]%mod;
}
void Init(){
	fac[0]=1;
	mi[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	invFac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)invFac[i]=invFac[i+1]*(i+1)%mod;
	for(int i=1;i<=n;i++)mi[i]=mi[i-1]*2%mod;
}
int main(){
	scanf("%lld",&n);Init();
	for(int i=n/2+1;i<=n;i++)sum=(sum+((C(n,i)*mi[n-i])%mod))%mod;
	sum=(qpow(3,n)-sum*2%mod+mod)%mod;
	printf("%lld\n",sum);
	return 0;
}
           

感受

就好巧妙的轉化，是我不配了嗚嗚嗚嗚嗚