SRM467 Div1 500 SuperSum

TopCoder

問題

  • SuperSum(0, n) = n
  • SuperSum(k, n) = SuperSum(k-1, 1) + … + SuperSum(k-1, n)
  • で定義されるSuperSum(k, n)の値を求める．kは50以下，nは10億以下


解いてみた

  • kが小さい場合を考えてみると
  • SuperSum(1, n) = n(n+1)/2
  • SuperSum(2, n) = n(n+1)(n+2)/6
  • となると…
  • SuperSum(k, n) = n(n+1)…(n+k)/(k+1)! か？
  • 実装してみたらシステムテストに通った．
  • あとで証明もちゃんと考えてみよう．
  • (追記)普通にコンビネーションじゃないか…
  • kが50以下ということは，他の解法もあるのかな？
#include <iostream>

using namespace std;

const int MOD = 1000000007;

class SuperSum{
private:
    long long pow(int t, int p){
        if(p == 0) return 1;
        if(p == 1) return t;
        long long tmp = pow(t, p/2)%MOD;
        tmp = (tmp*tmp)%MOD;
        if(p%2 == 0) return tmp;
        return (tmp*t)%MOD;
    }
    long long rev(int t){
        return pow(t, MOD-2);
    }
public:
    int calculate(int k, int n){
        long long res = n;
        for(int i=0;i<k;i++) res = (res*(n+i+1))%MOD;
        for(int i=2;i<=k+1;i++) res = (res*rev(i))%MOD;
        return (int)res;
    }
};