首页 algorithm 算法竞赛 CSP

# A - 装饰品

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

证明：

ab mod p=(a mod p)b mod (p−1)a^b\ mod\ p= (a\ mod\ p)^{b\ mod\ (p-1)}

ab mod p=a(p−1)k+h mod p=(ap−1)k mod p⋅ah mod p=ah mod pa^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)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;
}