lucas定理 學習筆記

文章目錄

• lucas定理 學習筆記
• • 介紹
  • combination
  • • 題目描述
    • 輸入格式
    • 輸出格式
    • 樣例
    • • 輸入樣例1
      • 輸出樣例2
  • 分析
  • code
• 擴展lucas

介紹

lucas定理用于解決形如 $C_n^m\mathrm{mod}p(p\in prime)$ 的問題。

設 $n,m$ 用 $p$ 進制來表示為：$(n_a{n}_{a?1}?n_0{)}_p,(m_a{m}_{a?1}?m_0{)}_p$

則：
$$C_n^m=C_{n_a}^{m_a}?C_{n_{a?1}}^{m_{a?1}}?C_{n_0}^{n_0}$$
例如下面這道題 oj

combination

題目描述

LMZ有n個不同的基友，他每天晚上要選m個一起玩，而且要求每天晚上的選擇都不一樣。那么LMZ能夠持續多少個這樣的夜晚呢？當然，LMZ的一年有10007天，所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)

輸入格式

第一行一個整數t，表示有t組數據。(t<=200) 接下來t行每行兩個整數n, m，如題意。

輸出格式

T行，每行一個數，為C(n, m) mod 10007的答案。

樣例

輸入樣例1

4 5 1 5 2 7 3 4 2

輸出樣例2

5 10 35 6

分析

顯然，答案就是：$C_n^m\mathrm{mod}10007$

但是我們的 $fac[],inv[]$ 開不了200,000,000，

所以我們就可以用 lucas 定理減小空間

code

#include <bits/stdc++.h> #define LL long long #define fu(x , y , z) for (int x = y ; x <= z ; x ++) #define fd(x , y , z) for (int x = y ; x >= z ; x --) using namespace std; const int mod = 10007; LL fac[mod + 5] , inv[mod + 5] , n , m; LL ksm (LL x , LL y) {if(!y)return 1;long long z = ksm (x , y / 2);z = z * z % mod;if (y & 1)z = z * x % mod;return z; } void pre () {fac[0] = fac[1] = 1;for(int i = 2 ; i <= mod - 1 ; i++)fac[i] = fac[i - 1] * i % mod;inv[mod - 1] = ksm (fac[mod - 1] , mod - 2);for (int i = mod - 2 ; i >= 0 ; i --)inv[i] = inv[i + 1] * (i + 1) % mod; } LL C (LL x , LL y) {if (x < y) return 0;if (!y || x == y) return 1;return fac[x] * inv[y] % mod * inv[x - y] % mod; } LL lucas (LL x , LL y) {if (x < y) return 0;if (!y) return 1;if (x < mod && y < mod) return C (x , y);return lucas (x / mod , y / mod) * C (x % mod , y % mod) % mod; } int main () {pre ();int T;scanf ("%d" , &T);while (T --) {scanf ("%lld%lld" , &n , &m);printf ("%lld\n" , lucas (n , m));} }

擴展lucas

未完待續

總結

以上是生活随笔為你收集整理的lucas定理 学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。