はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける数え上げ数学計算問題まとめ

数え上げ数学計算

問題

階乗の逆元をかけて計算する系

【発展的話題】 CRT(中国人剰余定理)とルーカスの定理を使うと解ける二項定理

問題1 解説
問題2 解説

前提知識
hamayanhamayan.hatenablog.jp

上記の2問題で求められる計算は
C(a,b) mod m
a,b <= 10^18, m<10^6(素数じゃないかも)
である。

計算手順
1. modを素因数分解する
2. 各素因数の累乗をmodとして二項定理を解く(uwiさんのサイトのこの部分の手法を使う)
3. それぞれ解けた答えでCRTを解くと答えが出る

【発展的話題】 ウィルソンの定理

N! mod Mを解くのに必要
(M-1)! ≡ -1 (mod M)という定理がウィルソンの定理