TopCoder SRM 467 Medium SuperSum

問題

supersum(k,n)を、
supersum(0,n)=n
supersum(k,n)=Σ[i=1 to n]supersum(k-1,i)
により定義する。

与えられた整数n,kに対してsupersum(n,k)をmod 10^9+7で求めよ。

制約条件

n≦10^9
k≦50

方針

小さい数で実験してみると、
supersum(n,k)はC(n+k,k+1)になっていることがわかる。

C(n+k,k+1)をmod 10^9+7で求めればよい。
10^9+7は素数であり、かつk+1が小さいので逆元から簡単にC(n+k,k+1)が求まる。

ソースコード

const int mod=(int)1e9+7;
ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d=1;
	if(b){
		d=extgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	else x=1,y=0;
	return d;
}
int inv(int n){
	ll x,y;
	extgcd(n,mod,x,y);
	return (x%mod+mod)%mod;
}
ll C(int n,int k){
	ll ret=1;
	rep(i,k)ret=ret*(n-i)%mod*inv(i+1)%mod;
	return ret;
}
class SuperSum {
	public:
	int calculate(int k, int n) 
	{
		return C(n+k,k+1);
	}
};