P10035 题解

sfqxx1 · 2024-01-02 20:01:19 · 题解

思路

刚开始看到这题没有思路，于是打了个表：

• 若 N 为 1 时：答案为 1。

• 若 N 为 2 时：

  答案为 4。

• 若 N 为 3 时：

  答案为 13。

于是，我们不难发现，答案为 \dfrac{3^{N}-1}{2} 。快速幂求出答案即可。

证明：

我们可以把 C 每 6 个字符分为一段，显然，一段内，答案为 3。又因为 C 的长度不含因数 6，但含因数 3，所以剩下的 3 个字符对答案的最小贡献为 1。

其实你也可以通过得数去验证。

代码

//by sfqxx1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

ll qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        ll a;
        cin >> a;
        ll res = qpow(3, a);
        ll i = mod - mod / 2;
        res = (res-1+mod) * i % mod;
        cout << res << endl;
    }
    return 0;
}