首页 > 代码库 > 算(tyvjP4700)

算(tyvjP4700)

背景

zhx和他的妹子出去玩。

描述

技术分享

请在此填写题目描述

输入格式

仅一行,包含两个数N和M.

输出格式

仅一行,包含所求的答案mod 10^9 + 7的值。

【样例输入】

3 3

【样例输出】

56

备注

对于 50%的数据,所有1≤N,M≤1000。

对于100% 的数据,所有1≤N,M≤50000 。

技术分享
/*  首先暴力枚举是(0)n^2的,考虑怎样优化成(0)n,我们对于每一排数,可以找到规律:  p=(pow(i,y+1)-1)/(i-1),然而本题需要取模,这样除法就会出错,所以利用费马小定理  和逆元的方法解决。    费马小定理:x^(p-1)%p=1    逆元:a*b%p=1,b是a在模p意义下的逆元  所以 p=(pow(i,y+1)-1)*pow(i-1,mod-2)       (分子和分母同时乘以 pow(i-1,mod-2))*/#include<cstdio>#include<iostream>#define ll long longconst ll mod=1e9+7;using namespace std;ll poww(int a,int b){    ll base=a,r=1;    while(b)    {        if(b&1)r*=base;        base*=base;        base%=mod;        r%=mod;        b/=2;    }    return r%mod;}int main(){    freopen("sum.in","r",stdin);    freopen("sum.out","w",stdout);    ll x,y,ans=0;    cin>>x>>y;    for(ll i=1;i<=x;i++)    {        if(i==1)ans+=y;        else        {            ll hou=poww(i,y+1);            ans+=((((hou-1+mod)%mod)*poww(i-1,mod-2)-1+mod)%mod);            ans%=mod;        }    }    cout<<ans%mod;    return 0;}
View Code

 

算(tyvjP4700)