题解 | #序列求和#

思路

本来纳闷这不就是求平方和，带公式就好了嘛？ $S(n)=\frac{n(n+1)(2n+1)}{6}$ ，过程中要不断取模避免出错。
不过结果还是不一样……突然想到我除了一个数，要用逆元呀~
因此公式应该改为 $S(n)=n(n+1)(2n+1)*inv(6)mod (1e9+7)$
就可以得到正确答案了~(可以提前算出6模1e+7意义下的逆元)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;

ll n,ans,tmp;

ll fpow(ll p,ll t){
    p%=mod;
    ll res=1;
    while(t){
        if(t&1) res=res*p%mod;
        p=p*p%mod;
        t>>=1;
    }
    return res%mod;
}

int main(){
    //fpow(6,mod-2)=166666668;
    while(cin>>n){
        ans=n%mod;
        ans=ans*((n+1)%mod)%mod;
        tmp=((n%mod)*2+1)%mod;
        ans=ans*tmp%mod;
        ans=ans*166666668%mod;
        cout<<ans<<endl;
    }
    return 0;
}