[ARC117C] Tricolor Pyramid

· · 题解

讲一种跟其他题解完全不同的构造。

令 B=1，W=2，R=4，构造 f(a,b)=(ab)^{-1}\bmod 7.

可以发现这是一种符合题意的构造。考虑模拟统计答案的过程，以 n=4 为例。

a_1,a_2,a_3,a_4 \Longrightarrow a_1^{-1}\cdot a_2^{-1},a_2^{-1}\cdot a_3^{-1},a_3^{-1}\cdot a_4^{-1} \Longrightarrow a_1\cdot a_2^2\cdot a_3,a_2\cdot a_3^2\cdot a_4 \Longrightarrow a_1^{-1}a_2^{-3}a_3^{-3}a_4^{-1}

我们要做的就是求 \displaystyle\prod_{i=1}^{n}a_i^{\binom{n-i}{i-1}} 模 7 的值。另外如果 n 为偶数，再对答案式求模 7 的逆。

因为组合数比较大可以用欧拉定理降幂，即将组合数对 6 取模。

对 2,3 分别 Lucas 一下合并就好了。时间复杂度 O(n\log_2 n +n\log_3 n).

如果 ARC 考场上像我这样做你就寄了

评测记录

#include<bits/stdc++.h>
#define N 400010
using namespace std;
int read(){
    int x=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*w;
}
int n;char s[N];
const int P=7;
int inv[P],a[N];
int qpow(int k,int b){
    int ret=1;
    while(b){
        if(b&1)ret=ret*k%P;
        k=k*k%P,b>>=1;
    }
    return ret;
}
int C2(int n,int m){
    if(n<0||m<0||n<m)return 0;
    return 1;
}
int L2(int n,int m){
    if(n<0||m<0||n<m)return 0;
    if(!n||!m)return 1;
    return L2(n/2,m/2)*C2(n%2,m%2)%2;
}
int C3(int n,int m){
    if(n<0||m<0||n<m)return 0;
    if(!n||!m||n==m)return 1;
    return 2;//n=2,m=1
}
int L3(int n,int m){
    if(n<0||m<0||n<m)return 0;
    if(!n||!m)return 1;
    return L3(n/3,m/3)*C3(n%3,m%3)%3;
}
int CRT(int x2,int x3){
    if(x3==0)return x2?3:0;
    if(x3==1)return x2?1:4;
    return x2?5:2;
}
void solve(){
    n=read(),scanf("%s",s+1);
    int ans=1;
    for(int i=1;i<=n;i++){
        a[i]=(s[i]=='B')?1:(s[i]=='W'?2:4);
        ans=ans*qpow(a[i],CRT(L2(n-1,i-1),L3(n-1,i-1)))%P;
    }
    if(!(n&1))ans=inv[ans];
    putchar(ans==1?'B':(ans==2?'W':'R'));
    printf("\n");
}
int main(){
    inv[1]=1,inv[2]=4,inv[4]=2;
    int T=1;
    while(T--)solve();

    return 0;
}