ARC117

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 inom{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]);
}