背景

zhx和他的妹子出去玩。

描述

技术分享

请在此填写题目描述

输入格式

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

输出格式

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

【样例输入】

3 3

【样例输出】

备注

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

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

题解：

等比数列：{a,aq₁,aq₂,aq₃,aq₄,aq₅...aq_n,...}

前m项的前缀和：s=a(1-q^m)/(1-m);

费马小定理：若p为质数，a^p-1%p=1

逆元：若ax%p=1(p为质数)，则a,x互为逆元

则ans=sigma（1,n）q(1-q^m)/(1-m)

由于同余定理不支持除法，逆元处理:

ans=sigma（1,n）q(1-q^m)/(1-q)^mod-2

考虑到负数问题

ans=sigma（1,n）q(q^m-1)/(q-1)^mod-2

最终

ans=sigma（1,n）q(q^m-1)/(q-1)^mod-2

代码：

#include<cstdio>#include<iostream>#define ll long longusing namespace std;const ll mod=1e9+7;ll n,m;inline ll fpow(ll a,ll p){    ll res=1;    for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;    return res%mod;}inline void solve(){    ll ans=n;    for(ll i=2,tmp,s;i<=n;i++){        /*自己推的*/         //tmp=fpow(i,m+1);        //s=((tmp-1+mod)%mod)*fpow(i-1,mod-2)%mod;        //ans=(ans+s-1+mod)%mod;        /*学哥讲的等比数列*/         tmp=i*(fpow(i,m)-1)%mod;        s=fpow((i-1),mod-2);        tans=(ans+tmp*s%mod)%mod;    }//应该是都对     cout<<ans%mod;}int main(){    ios::sync_with_stdio(false);    cin>>n>>m;    solve();    return 0;}

P4700 算

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > P4700 算