P10035题解

· · 题解

P10035题解

此题是一道找规律题。

将 A，B，C 前六位列出：

我们可以发现 ： 对于 A，B，C 中前六位的匹配字符的个数是相同的（均为三位）。

所以说，对于每一个 N，也就是 3^N 级台阶，我们都只需要判断最后三位求出最小的位数在加上前 6 \times n 中的匹配数字个数即可（其中 n 指满足 6 \times n 小于 3 ^ N 的 n 最大值）。

同样的，我们易知前三位中 A 与 C 的匹配个数最少，仅为一个。

由于 3 ^ N 向 3 取余一定为 3，所以相当于有 \frac {3 ^ N - 3} {6} 个长度为 6 的子序列和 1 个长度为 3 的子序列，其中，每个长度为 6 子序列中有 3 个匹配，长度为 3 的子序列最少有 1 个匹配。

故 ans = \frac {3 ^ N - 3} {6} （ 3 ^ N 向下取整） \times 3 + 1 = \frac {3 ^ N - 1} {2}。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, n, Mod = 1e9 + 7;
ll qmi(ll a, ll b)                  //快速幂
{
    ll res = 1 % Mod;
    while (b)
    {
        if (b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T -- )
    {
        cin >> n;
        ll a = (qmi(3, n) - 1) * qmi(2, Mod - 2);   //经典快速幂求逆元
        a %= Mod;
        cout << a << "\n";
    }
    return 0;
}