请用C++ 实现计算 a 的 b 次方对 1e9+7 取模以后的结果

可以使用快速幂算法来计算 a 的 b 次方，然后再对 1e9+7 取模。具体代码实现如下：

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

int powMod(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (long long) res * a % MOD;
        a = (long long) a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    int a, b;
    cin >> a >> b;
    int ans = powMod(a, b);
    cout << ans << endl;
    return 0;
}

其中，`powMod` 函数使用了快速幂算法来计算 $a^b$ 对 1e9+7 取模的结果。时间复杂度为 $O(\log b)$。

相关问题

给定一个整数n，有一棵n个节点的二叉搜索树，节点值依次为1,2,…,n。求这棵二叉搜索树有多少种可能的形状。 由于输出结果较大，故要求结果对1e9+7取模后输出 不失一般性，如果n=0，可能的形状为1 在不使用STL容器的情况下用C++实现

题目描述

给定一个整数n，有一棵n个节点的二叉搜索树，节点值依次为1,2,…,n。求这棵二叉搜索树有多少种可能的形状。

由于输出结果较大，故要求结果对1e9+7取模后输出

不失一般性，如果n=0，可能的形状为1

算法思路

此题为卡特兰数的经典应用，卡特兰数的递推公式为:

C[0] = C[1] = 1;
for (int i = 2; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
C[i] += C[j] * C[i - j - 1];

其中C[i]表示二叉搜索树有i个节点时的形状数。

时间复杂度

时间复杂度为 $O(n^2)$

空间复杂度

空间复杂度为 $O(n)$

C++代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

int n;
int f[N];

int main()
{
    cin >> n;

    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j < i; j ++ )
            f[i] = (f[i] + (long long)f[j] * f[i - j - 1]) % mod;

    cout << f[n] << endl;

    return 0;
}

小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列，使得该子序列中不包含连续的"61"子串。 小红想知道，有多少种不同的子序列选择方式？答案对 1e9+7取模。C++代码

以下是相同的动态规划思路的 C++ 代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

char s[MAXN];
int dp[MAXN];

int main() {
    cin >> s + 1;
    int n = strlen(s + 1);

    dp[0] = 1;
    int last_6 = -1;
    for (int i = 1; i <= n; i++) {
        if (s[i] != '6' && s[i] != '1') {
            dp[i] = (dp[i-1] * 2) % MOD;
        } else if (s[i] == '1' && last_6 >= 0) {
            dp[i] = (dp[i-1] * 2 - dp[last_6]) % MOD;
        } else {
            dp[i] = dp[i-1];
        }
        if (s[i] == '6') {
            last_6 = i;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + dp[i]) % MOD;
    }
    cout << ans << endl;

    return 0;
}