快速幂取模

问题 D: 生成树计数

时间限制: 1 Sec 内存限制: 128 MB
提交: 60 解决: 11
[提交][状态][讨论版]

题目描述

一个有n(n>=2)个点的完全无向图，冰语想知道这个图中有多少个不同的生成树(两棵生成树不同当且仅当生成树的边集不同)。你能告诉冰语吗？答案对1e9+7取模

输入

第一行为样例个数T(1<=T<=1e5),接下来T行每行一个正整数n,(2<=n<=1e18)

输出

输出T行，每行对应一个答案

样例输入

2
5
9

样例输出

125
4782969

思路：n个结点完全图的生成树个数是n^(n-2)，但是这里直接求幂O（n）超时，需要用到快速幂。
快速幂：对于a^b，带入b的二进制表示。例如b=11,b=1011,a^b=a^(2^0+2^1^3)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<vector>
 7 #define lson l, m, rt<<1
 8 #define rson m+1, r, rt<<1|1
 9 #define IO ios::sync_with_stdio(false);cin.tie(0);
10 #define INF 1e9
11 const int MOD=1e9+7;
12 typedef long long ll;
13 using namespace std;
14 ll n, m;
15 ll mod_pow(ll a, ll b)
16 {
17     ll r = a, ans = 1;
18     while(b){
19         if(b&1){
20             ans = (ans*r)%MOD;
21         }
22         r = (r*r)%MOD;//这里是r*r不是r*a 
23         b >>= 1;
24     }
25     return ans;
26 }
27 int main()
28 {
29     IO;
30     cin >> n;
31     while(n--){
32         cin >> m;
33         cout << mod_pow(m, m-2) << endl;
34     }
35     return 0;
36 }