重点

当ll乘ll时，会爆ll，所以要用快速乘

c++代码

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
#define ll long long
const ll maxn=1e5+10;
ll mod ;
const long long M=1000000007;
ll quickmul(ll a,ll b)
{
    ll ret = 0;
    for (; b; b >>= 1, a = (a << 1) % mod)
        if (b & 1)
            ret = (ret + a) % mod;
    return ret%mod;
}
ll bigpow(ll x, ll y)
{
    ll ret = 1;
    ll tmp = x%mod;
    while (y > 0)
    {
        if (y & 1)
        ret = quickmul(ret,tmp) %mod;
       y >>= 1;
        tmp = quickmul(tmp,tmp) %mod;
   }
    return ret%mod;
}