ARC117 - Tricolor Pyramid

设三种颜色分别为01,2, 容易发现原题变换$f(a,b)$的等价表达为

$f(a,b)=(-a-b)\mod 3$

$\mod 3$可以最后处理，那么就是一个取负操作

看成一个递推$F_{n,i}=col_i$

$F_{i,j}=-F_{i+1,j}-F_{i+1,j+1}$，求出$F_{1,1} \mod 3$

那么对于每个$col_i$，处理其对于$F_{1,1}$的贡献系数，容易发现贡献就是一个两边走的杨辉三角，即$\displaystyle \binom{n-1} {i-1}(-1)^{n-1}$

然后我就真的暴力处理组合数

const int N=1e6+10,INF=1e9+10;

int n;
char s[N];
char ch[]="BWR";

int F[N],cnt[N];
int C(int n,int m){
	if(cnt[n]-cnt[m]-cnt[n-m]) return 0;
	return F[n]*F[m]*F[n-m]%3;
}

int main(){
	rep(i,F[0]=1,N-1) {
		cnt[i]=cnt[i-1],F[i]=F[i-1];
		int x=i;
		while(x%3==0) x/=3,cnt[i]++;
		F[i]=F[i]*x%3;
	}
	scanf("%d%s",&n,s+1);
	int sum=0;
	rep(i,1,n) {
		int t=0;
		if(s[i]=='W') t=1;
		if(s[i]=='R') t=2;
		if(~n&1) t=3-t;
		sum=(sum+C(n-1,i-1)*t)%3;
	}
	sum%=3,putchar(ch[sum]);
}