C++14(g++5.4) 解法, 执行用时: 4114ms, 内存消耗: 612K, 提交时间: 2019-07-22 02:03:31

// Cease to struggle and you cease to live
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const LL MAXK=2e3;
LL invk,k,n;
LL p[MAXK],b[MAXK<<1],c[MAXK<<1],temp[MAXK<<1];
LL qp(LL a,LL b){
	LL re=1;
	for (;b;b>>=1){
		if (b&1) re=(re*a)%mod;
		a=a*a%mod;
	}
	return re;
}
void mul(LL *A,LL *B){
	for (int i=0;i<=(k<<1);i++) temp[i]=0;
	for (int i=0;i<=k;i++) if (A[i]!=0)
		for (int j=0;j<=k;j++) if (B[j]!=0)
			temp[i+j]=(temp[i+j]+A[i]*B[j])%mod;
	for (int i=(k<<1);i>=k;i--){
		if (temp[i]!=0)
			for (int j=0;j<k;j++)
				temp[i-k+j]=(temp[i-k+j]+temp[i]*invk)%mod;
		temp[i]=0;
	}
	for (int i=0;i<=k;i++) A[i]=temp[i];
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.precision(6); cout << fixed;
	int T;
	for (cin>>T;T;T--){
		cin>>k>>n;
		if (n==-1){
			cout<<2*qp(k+1,mod-2)%mod<<endl;
			continue;
		}
		invk=qp(k,mod-2);
		p[0]=1;
		for (LL i=1,sum=1;i<=k;i++) p[i]=sum*invk%mod,sum=(sum+p[i])%mod;
		if (k>=n){
			cout<<p[n]<<endl;
			continue;
		}
		for (int i=0;i<=(k<<1);i++) b[i]=c[i]=0;
		b[0]=1; c[1]=1;
		for (LL i=n;i;i>>=1){
			if (i&1) mul(b,c);
			mul(c,c);
		}
		LL ans=0;
		for (int i=0;i<k;i++) ans=(ans+(b[i]*p[i])%mod)%mod;
		cout<<ans%mod<<endl;
	}
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 2130ms, 内存消耗: 612K, 提交时间: 2019-07-22 08:59:32

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1050,P=1000000007;
ll pw(ll x,ll y=P-2){
    ll s=1;
    for(;y;y>>=1,x=1ll*x*x%P)
        if(y&1)s=1ll*s*x%P;
    return s;
}
ll i,w,x,b,j,t,a[M],c[M],v[M],u[M<<1],ans;
ll sol(ll n,ll m) {
    n+=m-1;
    for(i=m-1;~i;i--)c[i]=pw(m);
    for(i=0;i<m-1;i++)a[i]=0;a[m-1]=1;
    for(i=0;i<m;i++)v[i]=1;
    for(w=!!n,i=n;i>1;i>>=1)w<<=1;
    for(x=0;w;copy(u,u+m,v),w>>=1,x<<=1){
        fill_n(u,m<<1,0),b=!!(n&w),x|=b;
        if (x<m)u[x]=1;
        else {
            for(i=0;i<m;i++)for(j=0,t=i+b;j<m;j++,t++)u[t]=((ll)v[i]*v[j]+u[t])%P;
            for(i=(m<<1)-1;i>=m;i--)for(j=0,t=i-m;j<m;j++,t++)u[t]=((ll)c[j]*u[i]+u[t])%P;
        }
    }
    ans=0;
    for(i=0;i<m;i++)ans=((ll)v[i]*a[i]+ans)%P;
    return ans;
}
int T,k;ll n;
int main()
{

    for(scanf("%d",&T);T--;){
        scanf("%d%lld",&k,&n);
        if(n==-1)printf("%lld\n",2ll*pw(k+1)%P);
        else printf("%lld\n",sol(n,k)%P);
    }
    return 0;
}