C++14(g++5.4) 解法, 执行用时: 588ms, 内存消耗: 36984K, 提交时间: 2018-08-09 15:42:39

#include<bits/stdc++.h>
#define maxn 1555555

using namespace std;
typedef long long ll;
const ll M=1000000007;
ll ans,nf[maxn],f[maxn],inv[maxn],n,m,k,x,p,b,d;


ll pow_(ll x,ll y){
    ll rt=1;
    while (y){
        if (y&1) rt=rt*x%M;
        x=x*x%M;y>>=1;
    }
    return rt;
}
ll C(ll x,ll y){
    if (x<y) return 0;
    return 1ll*f[x]*nf[y]%M*nf[x-y]%M;
}

int main(){
    nf[0]=f[0]=1;inv[1]=1;
    for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
    for (int i=1;i<maxn;i++) nf[i]=1ll*nf[i-1]*inv[i]%M;
    for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M;
    cin >> n;
    for (int i=1;i<=n;i++) for (int j=1;j*i<=n;j++){
        d=n-i*j; b=i*j; x=i-1;
        (ans-=C(d+x+1,x+3)*(x+1)%M*(x+2)%M)%=M;
        (ans+=C(d+x+1,x+2)*(x+1)%M*(n-b*2-1))%=M;
        (ans+=C(d+x+1,x+1)*b%M*(n-b))%=M;
    }
    cout << (ans+M)%M << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 324ms, 内存消耗: 12140K, 提交时间: 2018-08-14 18:12:38

#include <bits/stdc++.h>
using namespace std;
#define Mod 1000000007
int f[1000001],inv[1000001],nf[1000001];
int n,ans,t;
long long C(long long a,long long b){
	if(a<b)return 0;
	return 1LL*f[a]*nf[b]%Mod*nf[a-b]%Mod;
}
int main(){
	inv[1]=1;
	f[1]=1;
	f[0]=1;
	nf[1]=1;
	nf[0]=1;
	for(int i=2;i<1000001;i++){
		inv[i]=Mod-1LL*(Mod/i)*inv[Mod%i]%Mod;
		f[i]=1LL*f[i-1]*i%Mod;
		nf[i]=1LL*nf[i-1]*inv[i]%Mod;
	}
	cin>>n;
	for(int d=1;d<n;d++){
		for(int k=2;k<=(n-1)/d+1;k++){
			t=(k-1)*(d-1)%Mod;
			ans=(ans+t*C(n-t,k)%Mod)%Mod;
			t=n-t;
			if(t<k)continue;
			ans=(ans+1LL*(t+1)*(k-1)%Mod*C(t,k)%Mod)%Mod;
			ans=(ans+Mod-1LL*k*(k-1)%Mod*C(t+1,k+1)%Mod)%Mod;
		}
	}
	cout<<(ans+Mod)%Mod;
}