naoya_t@topcoder

剰余とりながら計算するやつ

13:32 |

cafelier先生のコードからの抜粋

cf. https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20100416/1271391378

typedef long long LL;

LL M = 1000000007LL; // その時々で。素数でない場合は以下のDIV()が使えないことがある

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

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