P10035

yzm6677 · 2024-01-03 22:19:29 · 题解

写篇题解纪念一下在赛场上盲猜结论拿下的黄题。

思路

首先我们可以发现，把 01 串 C 每六个字符分成一段，对于每一段，无论采用哪种走法，都会踩到三次油漆。

而 3^n 显然为奇数，所以它并不能整除 6，而它又含有因数 3，所以分组后一定会剩下单独的长度为 3 的 01 串。

这个 01 串对答案的最小贡献为 1。

所以答案为 \lfloor \frac{3^n}{6} \rfloor \times 3 +1=\frac{3^n-3}{6} \times 3+1=\frac{3^n-1}{2}。

使用快速幂，复杂度 O(T \log n)。

#include <bits/stdc++.h>
using namespace std;
const long long p = 1000000007;
long long t, n;
long long pmod(long long a, long long b) { // 快速幂
    long long base = a, ans = 1;
    while(b > 0) {
        if(b & 1) ans = (ans * base % p) % p;
        base = (base % p * base % p) % p;
        b >>= 1;
    }
    return ans % p;
}
int main() {
    cin >> t;
    while(t--) {
        cin >> n;
        cout << ((pmod(3, n) - 1) % p * 500000004) % p << '\n';
        // 注意这里要用乘法逆元，我是先前已经求了
    }
    return 0; // 完结撒花（？
}

题外话（赛时的做法）

先是求了一下 n=1,2,3 时的答案发现分别是 1,4=1+3,13=1+3+9，然后直接大胆猜测应该输出 3^0+3^1+\dots+3^{n-1}=\frac{3^n-1}{2}，结果就过了。

upd：https://www.luogu.com.cn/discuss/758589