naoya_t@topcoder

SRM467

12:08 |

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	LateProfessor	提出	-	撃沈	-	0.0
1	500	SuperSum	間に合わず	-	-	-	-
1	1000	-	-				-

Easy(250): LateProfessor

• 歩いて帰ってきてからwaitするのに気づかずはまる

Medium(500): SuperSum

• TLEで提出できないー

Hard(1000): 開いてない

Challenge Phase:

• 250撃沈される
  • 最初の待ち時間の間にしか先生が来ないケースで死ぬお＞＜
• cafelier先生の500のコード見る。なにこれ簡単
  • 自分のメモを45度回転させて見たらそのままあれだった
  • と思ったけど MUL(x, POW(y, MODVAL-2)) を理解してない

// cafelier先生の500のコードから
static const LL MODVAL = 1000000007;

LL ADD(LL x, LL y) { ... } // (x + y) % MODVAL
LL SUB(LL x, LL y) { ... } // (x - y) % MODVAL
LL MUL(LL x, LL y) { ... } // (x * y) % MODVAL
LL POW(LL x, LL y) { ... } // (x ^ y) % MODVAL
LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); } // (x / y) % MODVAL ←ここ

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

• ああそうか、フェルマーの小定理 POW(y,MODVAL-1)≡1 の両辺にx/y（これは整数を仮定していいのかな）を掛けてMODVALで剰余をとった感じか
• それはMODVALが素数でないと成り立たない？

Result:

0 point

Room: 14/20

Div I: 282/521

1370 → 1342 (-28) 転落し続ける…

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

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; }