Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-04-16

SRM467

12:08 | SRM467 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM467 - naoya_t@topcoder SRM467 - naoya_t@topcoder のブックマークコメント

DIVlevel問題名競技中後で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) 転落し続ける…

http://gyazo.com/0396cc42692a450b2ad3456e7c00a93d.png

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

13:32 | 剰余とりながら計算するやつ - naoya_t@topcoder を含むブックマーク はてなブックマーク - 剰余とりながら計算するやつ - naoya_t@topcoder 剰余とりながら計算するやつ - naoya_t@topcoder のブックマークコメント

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

cf. http://topcoder.g.hatena.ne.jp/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; }

cafeliercafelier2010/04/16 13:28素数でないと成り立たないです。

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)
こんな感じ

cafeliercafelier2010/04/16 13:37素でない場合はそもそも先にmodを取ってしまうと情報が落ちて割り算が不可能になってしまうので、パスカルの三角形か何かで、割り算を回避して式を立てる必要があります。

n4_tn4_t2010/04/16 13:51腑に落ちました。どうもありがとうございます!

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100416