AT_arc117_c [ARC117C] Tricolor Pyramid 题解

HappyJaPhy · 2023-12-02 23:50:25 · 题解

• [ARC117C] Tricolor Pyramid
• 博客阅读体验 （也许） 更佳

  题意

• 给一个金字塔的底部颜色组成和生长规律，问顶部的颜色是什么。

分析

• 试几次就可以很容易得到的一种构造：令颜色 B 为 0，W 为 1，R 为 2。设左右两个方块的颜色分别为 col_l 和 col_r，则生长规则可以描述为 col_{now}\equiv-(col_l+col_r)\pmod 3。因为底部每一个元素有 C_{n-1}^{i-1} 种方式贡献到顶部元素上（一共要走 n-1 步，其中有 i-1 步是向左走，因此是 C_{n-1}^{i-1}），于是顶部元素颜色的表达式就出来了。 col_{top}\equiv(-1)^n\sum_1^n{C_{n-1}^{i-1}col_i}\pmod3
• 这里的 p 很小，因此组合数直接用 Lucas 求解即可。

代码

#include <bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
int n, a[N], ans;

inline int C(int n, int m) {
    if (n < m) return 0;
    int res = 1;
    for (int i = n - m + 1; i <= n; i++) res *= i;
    for (int i = 1; i <= m; i++) res /= i;
    return res % 3;
}

int Lucas(int n, int m) {
    if (m == 0) return 1;
    return Lucas(n / 3, m / 3) * C(n % 3, m % 3) % 3;
}

signed main() {
    scanf("%lld", &n);
    char ch = 0;
    while (ch < 'A' || ch > 'Z') ch = getchar();
    for (int i = 1; i <= n; i++) {
        if (ch == 'B') a[i] = 0;
        if (ch == 'W') a[i] = 1;
        if (ch == 'R') a[i] = 2;
        ch = getchar();
    }
    for (int i = 1; i <= n; i++) {
        ans += Lucas(n - 1, i - 1) * a[i] % 3;
        ans %= 3;
    }
    if ((n & 1) == 0) ans = (3 - ans) % 3;
    if (ans == 0) printf("B");
    if (ans == 1) printf("W");
    if (ans == 2) printf("R");
    return 0;
}