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) 転落し続ける…