首页 > 代码库 > 算(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;}
算(tyvjP4700)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。