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;
}
