Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-31練習

SRM 467 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10239&rd=14151:title=SRM 467 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10239&rd=14151:title=SRM 467 Div1 Medium] - shnyaの参戦記録

下記の式で与えられるSuperSumを求める問題。

SuperSum(0 , n) = n, for all positive n.
SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.

1 <= k <= 50
1 <= n <= 1000000000

ノートに向かって1時間程悩むがギブアップ。Editorial見ると答えはパスカルの三角形になっているらしい。。。

こういう問題の場合、小さい集合で簡単にコード書いて計算してみるのがよさそうな気がしてきた。

剰余ライブラリは下記URLに書かれた先輩方から頂きました。

http://topcoder.g.hatena.ne.jp/n4_t/20100416/1271392320

http://topcoder.g.hatena.ne.jp/cafelier/20100416/1271391378

typedef long long int LLI;

LLI M = 1000000007LL;

LLI MUL(LLI x, LLI y) { return x*y % M; }
LLI POW(LLI x, LLI e) { LLI v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
LLI DIV(LLI x, LLI y) { return MUL(x, POW(y, M-2)); }

LLI C(LLI n, LLI k) { LLI v=1; for(LLI i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

class SuperSum {
public:
   int calculate( int k, int n ) {
     return C(n+k,k+1);
   }
};