2010-04-16
SRM467
| 
| DIV | level | 問題名 | 競技中 | 後で | System Test | 通過率 | 備考 |
|---|---|---|---|---|---|---|---|
| 1 | 250 | LateProfessor | 提出 | - | 撃沈 | - | 0.0 |
| 1 | 500 | SuperSum | 間に合わず | - | - | - | - |
| 1 | 1000 | - | - | - |
剰余とりながら計算するやつ
| 
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; }
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100416
2010-03-12
Codeforces Beta Round #4
Codeforces | | 
- http://codeforces.com/
- 初参戦
- registerしといたけど歯医者に寄って帰ったら21:15…
- やめとくか
- だが参加する
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100312
2010-03-09
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100309
m(x)=x%MODVALとして、m(x)とm(y)からm(x/y)を求めたいわけなので
x/y=z ⇔ x=zy ⇒ m(x)=m(z)m(y) ⇒ m(x)m(y)^{MODVAL-2}=m(z)m(y)^{MODVAL-1} ⇒(フェルマーの小定理より)⇒ m(x)m(y)^{MODVAL-2}=m(z)
こんな感じ