A-装饰品

  1. 根据分析，在第一个盒子有m中放发，第二个盒子有\(m-1\)种放发，在第三个盒子有\(m-2\)种放发，在第四个盒子，我们也只需保证和第2、3两个盒子中的不同即可，即\(m-2\)种选法，所以答案应该是\(m(m-1)(m-2)^{n-2}\)
  2. 显然我们需要用快速幂，但是\(n,m\)的范围很大，我们需要先对它们取模
  3. \(\color{red}{费马小定理：当p是质数且a不是p的倍数，a^{p-1}\equiv 1(mod\ p)}\)

证明：

\[a^b\ mod\ p= (a\ mod\ p)^{b\ mod\ (p-1)}\]

\[a^b\ mod\ p=a^{(p-1)k+h}\ mod \ p = (a^{p-1})^k\ mod \ p\cdot a^h\ mod\ p=a^h\ mod\ p\]

\[h = b\ mod\ (p-1)\]

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>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll T, m, n;
int qmi(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        m = m % mod, n = n % (mod - 1);//??????为什么必须要在这里取模？？？？？？？，不能再qmi那里取模？？？？？？
        if(n == 1) cout << m % mod << '\n';
        else
            cout << m % mod * (m - 1) % mod * qmi(m - 2, n - 2, mod) % mod<< '\n';
    }
    return 0;
}