石头剪刀布
题目描述
石头剪刀布的游戏，每一轮可以出三种招数：石头、剪刀、布。给定一个整数 NNN，表示需要进行 NNN 轮游戏。若规定每一轮出招不能与上一轮重复，请统计有多少种不同的出招序列？由于答案可能很大，输出答案模 1,000,000,0071,000,000,0071,000,000,007 的余数。
输入格式
单个整数 NNN
输出格式
输出答案模 1,000,000,0071,000,000,0071,000,000,007 的余数。
数据范围
- 对于 30%30\\%30% 的数据，1≤N≤101 \\le N \\le 101≤N≤10
- 对于 60%60\\%60% 的数据，1≤N≤1,0001 \\le N \\le 1,0001≤N≤1,000
- 对于 100%100\\%100% 的数据，1≤N≤1,000,000,0001 \\le N \\le 1,000,000,0001≤N≤1,000,000,000
样例数据
输入：
3
输出：
12
题解
我先来分析这道石头剪刀布的数学规律，再讲解代码思路。
一、题目分析
游戏有石头、剪刀、布共3种出法，规则是相邻两轮不能出一样的招数，求 N 轮的总出招序列数，结果对 109+710^9+7109+7 取模。
题目中 NNN 最大到 10910^9109，普通循环会超时，所以我选择**快速幂（二分幂）**来高效计算 2N−12^{N-1}2N−1。
二、完整带注释代码
#include<bits/stdc++.h>
using namespace std;
// 模数 1e9+7
const int mod = 1e9+7;
int main() {
int n;
// 读入游戏轮数 n
cin>>n;
// 公式：3 * 2^(n-1)，先把答案初始化为第一轮的3种选择
long long ans = 3;
// base底数，也就是每一轮可选的2种出法
long long m = 2;
// 计算指数 n-1，所以先让n自减1
n—;
// 快速幂核心循环，计算 m^n 并乘到 ans 上
while(n > 0){
// 如果当前二进制位为1，将当前底数乘入答案
if (n % 2){
ans *= m;
// 每次运算都取模，防止数据溢出
ans %= mod;
}
// 底数平方，二分降幂
m *= m;
m %= mod;
// 右移一位（等价于 n /= 2）
n /= 2;
}
// 输出最终结果
cout<<ans;
return 0;
}
