power oj 2608: 数学涛之神奇卡片---(快速幂取模)

Time Limit: 1000 MS Memory Limit: 65536 KB

快速幂 数学

Description

有n张卡片，编号为1到n，每张卡片上的数可能是1到m中的任意一个，最后得分是所有卡片上的最大值，问最大值是m的方案数。编号相同的卡片上数不同则方案不同。答案可能很大，对10^9+7取模。

Input

每一行有n,m代表n张卡，每张卡可能是1到m,(1≤n，m≤10^6)

Output

每行表示方案数

Sample Input

1 1
2 2

Sample Output

1
3

解题思路：

(1)、排列组合推一下就可以发现是这样的规律：
    如5张卡片，3个数：有最大值3的方案数为：3*3*3*3+2*3*3*3+2*2*3*3+2*2*2*3+2*2*2*2;然后就可以用快速幂来写，然而这样写超时了。。。。所以有了下一种方法
（2）、n张卡片,m个数可以组成的总共的方案数为m^n;
则可以这样算：用方案总数-没有最大的数的方案数，即：m^n-m^(n-1).

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1000000000+7;
ll quick(ll x,ll y)
{
    ll ans=1;
    ll temp=x%mod;
    while(y>0)
    {
        if(y&1)
            ans=(ans*temp)%mod;
        temp=(temp*temp)%mod;
        y=y>>1;
    }
    return ans;
}
int main()
{
    ll n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        ll ans1=0,ans2=0;
        ans1=quick(m,n)%mod;
        ans2=quick(m-1,n)%mod;
        ll ans=ans1-ans2;
        if(ans1<ans2)
            ans+=mod;///如果ans1-ans2为负数的时候；
        printf("%lld\n",ans);
    }
    return 0;
}