C - Tricolor Pyramid

考场上这题没做出来……

想要快速求解似乎有点困难，我们考虑通过某种运算。
将三种颜色编号为 ，两个方块上方的方块的颜色是 。（想出来完全靠直觉）

因此我们考虑讨论最上方的颜色值的正负和 的和。

正负：有上面的柿子得知，向上推奇数层是负的，偶数层是正的。

的和：讨论最下面的数值在最上方被加了几次。

因为一个方块的值会被与它相连的上方的方块加，最上方与它有几条路径，它就会被加几次。

由路径你想到了啥？杨辉三角！组合数！
用 Lucas 定理和费马小定理求出组合数 便是次数！对于底层的每一个方块都算一下就可以了。

参考代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
ll t,m,p=3,fac[500010];

inline ll ksm(ll a,ll b,ll p){
    ll ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
ll C(ll n,ll m){
    if(m>n) return 0;
    return fac[n]*ksm(fac[m],p-2,p)%p*ksm(fac[n-m],p-2,p)%p;
}
ll LucasDP(ll n,ll m){
    if(m==0) return 1;
    return LucasDP(n/p,m/p)*C(n%p,m%p)%p;
}// 不会的左转 Lucas 定理
int n; char ch[500010];
int main(){
    fac[1]=fac[0]=1;
    for(int i=2;i<=500000;i++) fac[i]=fac[i-1]*i%3; //预处理阶乘
    cin>>n>>(ch+1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll tmp=LucasDP(n-1,i-1); // 求被加的次数
        if(ch[i]=='B') tmp*=0;
        if(ch[i]=='W') tmp*=1;
        if(ch[i]=='R') tmp*=2;
        ans+=tmp; ans%=3; // 累加答案
    }
    if(n%2==0) ans=(3-ans)%3; // 正负
    if(ans==0) puts("B");
    if(ans==1) puts("W");
    if(ans==2) puts("R");
    return 0;
}