マツシタのお勉強

フェルマーの小定理

重複組合せを用いた多重ループ

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 問題文の以下に注目 このプログラムの出力する答えは 1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数に等しい 公式の解説に則ってこの文章を以下のように変換して考える。 「…

フェルマーの小定理による組み合わせ計算によって経路数を数え上げる

問題 D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder 解法 まず、この問題のポイントを抑える 問題のポイント 右と下にのみ移動可能なマス目の経路数の数え上げ 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105) AB…

フェルマーの小定理を用いてコンビネーションを計算する

背景 nCk nCkを計算したい。(n個の中からkこ取り出す組み合わせ) nCkはnCk = n! / k! * (n - k)!となる。これを計算すれば求まる。しかし、分母のk! * (n - k)!の部分に着目した時に、nの値が大きいと値が大きすぎて計算できない。 そこで、プロコンの世界で…