题目传送门：[ARC117C] Tricolor Pyramid
评价：不难，但是启发了我的思维
首先，这种题要明确的一点就是：从规律入手
我们发现规律要分类讨论，那么这就很难受，因为要分类讨论就代表这个规律不满足结合律，难以优化
这个时候我们常用的套路就是：构造一个等价的规律，并且这个规律不需要分类讨论或满足结合律。
这里给出一种构造的方式：
定义每种颜色有一个权值： \(B=0,W=1,R=2\)，则任意两个颜色 \(a,b\) 上方居中的位置的权值为：\((2\times (a'+b'))\bmod 3\)，其中 \(a',b'\) 为 \(a,b\) 颜色的权值
例如：现在有 \(BR\)，则它们上方居中的位置为 \((2\times (0+2))\bmod 3=1\)，所以他们上方居中的位置颜色为 \(W\)
我们发现，如果我们知道这个颜色，就可知道这个颜色的权值，反之，如果我们知道这个颜色的权值，就可以知道这个颜色。
现在考虑第 \(n\) 层颜色的权值为 \(a_1,a_2,a_3,...,a_n\)
则第 \(n-1\) 层颜色的权值为 \((2\times(a_1+a_2))\bmod 3,(2\times(a_2+a_3))\bmod 3,..,(2\times(a_{n-1}+a_n))\bmod 3\)
第 \(n-2\) 层颜色的权值为 \((4\times(a_1+2\times a_2+a_3))\bmod 3,(4\times(a_2+2\times a_3+a_4))\bmod 3,..,(4\times(a_{n-2}+2\times a_{n-1}+a_n))\bmod 3\)
\(......\)
第 \(1\) 层颜色的权值为 \((2^{n-1}\times (\binom{n-1}{0}\times a_1+\binom{n-1}{1}\times a_2+...+\binom{n-1}{n-1}\times a_n))\bmod 3\)
求组合数的时候用到 \(lucas\) 定理 \(+\) 递归就好了，这里不多做扩展，这里想讲的就只有遇到这种题的思路和这种构造。
贴个\(oi-wiki\)的传送门：Lucas定理
上代码：
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+50,mod=3;
int T,n,ans,ans1;
char s[N];
int C[5][5];
int ksm(int ds,int zs)
{
int re=1;
while(zs)
{
if(zs&1) re=(re*ds)%mod;
ds=(ds*ds)%mod;
zs=zs/2;
}
return re;
}
int zh(int m,int n)
{
if(m==n) return 1;
if(m<n) return 0;
if(n<3&&m<3) return C[m][n];
return zh(m/mod,n/mod)*zh(m%mod,n%mod)%mod;
}
int pd1(char x)
{
if(x=='B') return 0;
if(x=='W') return 1;
if(x=='R') return 2;
}
char pd(int x)
{
if(x==0) return 'B';
if(x==1) return 'W';
if(x==2) return 'R';
}
int main()
{
C[0][0]=1;
C[1][0]=1;
C[1][1]=1;
C[2][0]=1;
C[2][1]=2;
C[2][2]=1;
scanf("%d %s",&n,s+1);
ans=ksm(2,n-1);
ans1=0;
for(int i=1;i<=n;i++)
ans1=(ans1+zh(n-1,i-1)*pd1(s[i]))%mod;
printf("%c\n",pd((ans*ans1)%mod));
return 0;
}