https://atcoder.jp/contests/abc151/tasks/abc151_e
二項係数の高速化が必要なので復習を(今回はpが素数で)
まず、二項係数の計算を割り算ではなく、-1乗(逆元)としてnCk ＝ n! * (𝑘!)−1 * ((𝑛−𝑘)!)−1として計算する。
また、このとき逆元を利用する必要がある。
mod p における a の逆元 x を求めるために、拡張ユークリッドの互除法を使う
ax≡1(modp)としたときのxがaの逆元(mod p)。 よって、
ax+py=1の解(x, y)を拡張ユークリッドの互除法により解(x, y)を求める。→xがaの逆元になっている
これは、ax+py=1が(mod p)で、ax≡1となるから。
よって、xを求めることが逆元を求めるに等しい。
こんな感じで逆元を求めれば良い。
ただ、階乗の逆元を求めるのがやばいので、逆元テーブルを作るような方法が良い。
この問題に関してはここまでやれればokだったので一区切り。
余談だが、python、今ならpow(x,-1,mod)で逆元求められるかも(計算量がどうかは知らない)
C - バームクーヘン (Baumkuchen) 9:59 自力AC、嬉しい〜〜〜
A - JOI 紋章 (JOI Emblem) 11:51 考察3分、実装1時間強 実装の手順をもっと考えたほうがいいかも
C - 億マス計算 23:28 チートACに近い気がするな
忙しくてあまり解けなかった
D - 1 年生 (A First Grader) 10:31
A - 勇者ビ太郎 (Bitaro the Brave) 11:54
D - 星座探し 14:02
D - 最悪の記者 20:09 トポロジカルソート、俺には難しかったよ
A - JJOOII (JJOOII) 7:43 事故を起こしていたそうです
C - 夜店 (Night Market) 8:33 分割は考えたけどその先が詰まった
https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B 10:46 ベルマンフォードくん
D - Score Attack 11:48 見事に引っかかっていた、ただベルマンフォードを投げるだけじゃダメだった、考察・・・
A - IOIOI 14:29 1WA、マジで一回はWA出すなあ;;
mall - ショッピングモール (Mall) 18:59 入力間違えてた、信じられません
A - 往復すごろく (Round Sugoroku) 21:27 オーバーフローしてました
pyramid - 貫きピラミッド (Pyramid) 9:33 完全に一つのマスに重なって置かれるパターンを想定していなかった、想像力の欠如・・・・
D - バスと避けられない運命 10:09 ワーシャルフロイド〜^(気さくな挨拶)
D - joisino's travel 14:05 モチベの低下がやばい
D - Wall 14:44
Aizu Online Judge 17:31 せめて今日中に最小全域木だけでもという考え
D - Built? 20:55 読んで納得。
D - Game on a Grid 22:51 バグの場所見間違えて1時間強彷徨った。辛かった。
もう一問解こうとしたけどダメそう、寝ます
building - ビルの飾り付け (Building) 7:17 おはようございます
E - 品質検査 9:19 はい
F - 通学経路 10:05 はい 2
B - 最長の階段 11:20 a
C - 桁和 (Digit Sum) 13:30 すぐ解けたけど1度1000000個の配列で作ったから1000000番目が設定されなくてWAした。危ない。
用事があった
A - 長いだけのネクタイ (Just Long Neckties) 0:10 これすら難しく感じた、間に合うのか 0LLじゃないとダメって初めて知った、考察はできても実装が危うい(pair、配列の使い方が下手)
