以下摘要由GPT-4o生成:
在这个问题中，魔术师小蓝通过对三个红包中的金币数量进行 N 次变换来展示一个红包魔术。每次变换会将每个红包的金币数更改为其他两个红包金币数的乘积。给定初始的 A、B、C 和变换次数 N，目标是计算 N 次变换后这三个红包金币数量的总乘积，并对 1e9+7 取模以避免结果过大。题目涉及使用费马小定理来简化计算过程，以提高效率。输入包括多个测试用例，每个用例提供初始金币数和变换次数。

题目链接[6.春晚魔术【算法赛】 - 蓝桥云课]

问题描述

在蓝桥卫视春晚的直播现场，魔术师小蓝表演了一个红包魔术。只见他拿出了三个红包，里边分别装有 A、B 和 C 个金币。而后，他挥动魔术棒，念动咒语“福禄寿喜财神到～”，对红包里的金币进行 N 次变换。每次变换，每个红包的金币数量都会变成其他两个红包金币数量的乘积。

例如：

  • 初始金币数量 A=2, B=3，C=5，进行 N*=1 次变换后，金币数量变为 15，10，6。
  • 初始金币数量 A=1，B=2，C=3，进行 N=2次变换后，金币数量变为 6，12，18。

变换结束后，小蓝得意地问观众：“现在，你们知道三个红包里金币的总乘积是多少吗？” 他飞快地心算了一下，并报出一个数字：“让我来揭晓答案吧！总乘积是…嗯…（不知道算没算对，只知道算得快）”。

作为观众，请你计算 N 次变换后，三个红包金币数量的总乘积。由于结果可能很大，请输出其对 1e9+7取模的结果。

输入格式

第一行包含一个整数 T (1≤T≤103)，表示测试用例的数量。

接下来的 T* 行，每行包含四个整数 A，B，C* 和 N*（1≤A,B,C,N≤1e9），表示一组数据。

输出格式

对于每组数据，输出一个整数，表示 N* 次变换后三个红包金币数量的总乘积。由于结果可能很大，请输出其对 1e9+7 取模的结果。

样例输入

1
2
3
2
2 3 5 1
1 2 3 2

样例输出

1
2
900
1296

前置知识:

问题涉及利用费马小定理对指数进行降级的数学原理。以下是详细解释：

核心数学原理

当模数 p 是质数时，根据费马小定理 ，对任意整数 a 不被 p 整除，有：

a**p−1≡1(modp)

因此，对于任意指数 b，可以将其简化为 bmod(p−1)，即：

a**b≡a**bmod(p−1)(modp)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>

using namespace std;
#define int unsigned long long 
const int MOD = 1e9 + 7;
int qmi(int x, int k, int MOD){
  int res = 1;
  while (k) {
    if (k & 1) res = res * x %MOD;
    x = x * x % MOD;
    k >>= 1;
  }
  return res % MOD;
}
signed main(){
  int T;
  cin >> T;
  while (T--) {
      int a, b, c, n;
      cin >> a >> b >> c >> n;
      int k = qmi(2, n, MOD - 1);//费马小引理;
      int x = a % MOD;
        x = (x * (b % MOD)) % MOD;
        x = (x * (c % MOD)) % MOD;
      int res = qmi(x, k, MOD) % MOD;
      cout << res << endl;
  }

  return 0;
}