石头剪刀布

题目描述

石头剪刀布的游戏，每一轮可以出三种招数：石头、剪刀、布。给定一个整数 $N$，表示需要进行 $N$ 轮游戏。若规定每一轮出招不能与上一轮重复，请统计有多少种不同的出招序列？由于答案可能很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

单个整数 $N$

输出格式

输出答案模 $1,000,000,007$ 的余数。

数据范围

• 对于 $30\%$ 的数据，$1\le N\le 10$
• 对于 $60\%$ 的数据，$1\le N\le 1,000$
• 对于 $100\%$ 的数据，$1\le N\le 1,000,000,000$

样例数据

输入：

3

输出：

12

题解

我先来分析这道石头剪刀布的数学规律，再讲解代码思路。

一、题目分析

游戏有石头、剪刀、布共3种出法，规则是相邻两轮不能出一样的招数，求 N 轮的总出招序列数，结果对 $10^9+7$ 取模。

1. 第 1 轮：没有上一轮限制，一共有 3 种选择。
2. 从第 2 轮开始：每一轮都不能和上一轮相同，每轮都只有 2 种选择。
3. 总方案数公式：$ans=3\times 2^{N-1}$。

题目中 $N$ 最大到 $10^9$，普通循环会超时，所以我选择**快速幂（二分幂）**来高效计算 $2^{N-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;
}

三、思路总结

1. 我先推导出数学公式：总方案数 = $3\times 2^{n-1}$。
2. 因为数据范围极大，$n$ 可达 $10^9$，所以不能暴力循环乘 $n-1$ 次，改用快速幂优化时间复杂度到 $O(\log n)$。
3. 快速幂过程中，我全程对 $10^9+7$ 取模，避免长整型溢出，保证计算合法。
4. 以样例输入 3 举例：$3\times 2^2=12$，和样例输出一致，验证思路正确。