アルゴリズムと数学 102

https://atcoder.jp/contests/math-and-algorithm/tasks/arc117_c

手を動かした方がいい問題ってありますよね。
B → 0, W → 1, R → 2
と読み替えて、下がxとyだった時に上をf(x, y)と表すと、

f(0, 0) = 0 f(0, 1) = 2 f(0, 2) = 1
f(1, 0) = 2 f(1, 1) = 1 f(1, 2) = 0
f(2, 0) = 1 f(2, 1) = 0 f(2, 2) = 2

つまり、

となります。符号を無視すれば足しているだけです。足しているだけなら、abcの2つ上は、
となります。abcdの3つ上は、となります。一般に、のN-1上は、

となります。
ただ、3の剰余なので、Cの計算が少しややこしいです。いつものとかなら簡単なのですが。
から計算していくのですが、その際3がいくつ残っているかを記憶しておきます。3が1つ以上残っていれば0です。
符号は最後にNの偶奇で決めます。

// Tricolor Pyramid
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// Exp ////////////////////

use std::ops::{Mul, Div};

#[derive(Copy, Clone)]
struct Exp {
    f: i32,
    e: i32
}

impl Mul for Exp {
    type Output = Self;
    
    fn mul(self, other: Self) -> Self {
        Self { f: self.f * other.f % 3, e: self.e + other.e }
    }
}

impl Div for Exp {
    type Output = Self;
    
    fn div(self, other: Self) -> Self {
        Self { f: self.f * other.f % 3, e: self.e - other.e }
    }
}

impl Exp {
    fn new(n: i32) -> Exp {
        let f = n % 3;
        if n == 0 {
            Exp { f: 0, e: 0 }
        }
        else if n % 3 != 0 {
            Exp { f, e: 0 }
        }
        else {
            (Exp { f: 1, e: 1 }) * Exp::new(n/3)
        }
    }
    
    fn remainder(&self) -> i32 {
        if self.e != 0 {
            0
        }
        else {
            self.f
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> String {
    let _N: usize = read();
    let s = read();
    s
}

fn encode(c: char) -> i32 {
    match c {
        'B' => 0,
        'W' => 1,
        _   => 2
    }
}

fn decode(n: i32) -> char {
    match (n % 3 + 3) % 3 {
        0 => 'B',
        1 => 'W',
        _ => 'R'
    }
}

fn make_C_table(N: usize) -> Vec<i32> { 
    let mut Cs: Vec<i32> = vec![1; N as usize];
    // 1..N+1をf*3^eの形にする
    let a: Vec<Exp> = (0..N).map(|n| Exp::new(n as i32)).collect();
    let mut c = a[1];
    for i in 1..N {
        c = c * a[N-i] / a[i];
        Cs[i] = c.remainder()
    }
    Cs
}

fn F(s: String) -> char {
    let cs: Vec<i32> = s.chars().map(|c| encode(c)).collect();
    let N = cs.len();
    let Cs = make_C_table(N);
    let s = cs.into_iter().zip(Cs.into_iter()).map(|(n, C)| n*C).sum::<i32>();
    if N % 2 == 0 {
        decode(-s)
    }
    else {
        decode(s)
    }
}

fn main() {
    let s = read_input();
    println!("{}", F(s))
}