侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【排列组合, Lucas定理】求组合数 III

GabrielxD
2023-03-22 / 0 评论 / 0 点赞 / 342 阅读 / 746 字
温馨提示:
本文最后更新于 2023-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

887. 求组合数 III - AcWing题库


给定 nn 组询问,每组询问给定三个整数 a,b,pa, b, p ,其中 pp 是质数,请你输出 CabmodpC_a^b \bmod p 的值。

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含一组 a,b,pa, b, p

输出格式

nn 行,每行输出一个询问的解。

数据范围

1n201 \le n \le 20 ,
1ba10181 \le b \le a \le 10^{18} ,
1p1051 \le p \le 10^5 ,

输入样例:

3
5 3 7
3 1 5
6 4 13

输出样例:

3
3
2

解题

方法一:Lucas 定理 逆元 快速幂

Lucas 定理

Lucas 定理内容如下:对于质数 pp,有:

Cnm(Cnmodpmmodp)(Cn/pm/p)(modp)\mathrm{C}_{n}^{m} \equiv (\mathrm{C}_{n \bmod p}^{m \bmod p}) \cdot (\mathrm{C}_{\lfloor n / p \rfloor}^{\lfloor m / p \rfloor}) \pmod{p}

也就是说:

Cnmmodp=CnmodpmmodpCn/pm/pmodp\mathrm{C}_{n}^{m} \bmod p = \mathrm{C}_{n \bmod p}^{m \bmod p} \cdot \mathrm{C}_{\lfloor n / p \rfloor}^{\lfloor m / p \rfloor} \bmod p

证明咱不会(

思路

本题询问数量很少, a,ba, b 范围特别大,且模数 pp 较小,适合用 Lucas 定理求解。

具体来说:

  • a < p \and b < p ,那么直接从定义出发,使用公式求解:

    Cnm=n!m!(nm)!=i=nm+1nim!=n(n1)(nm+2)(nm+1)1×2××m\mathrm{C}_n^{m} = \frac{n!}{m!(n-m)!} = \frac{\prod_{i=n-m+1}^{n} i}{m!} = \frac{n(n-1) \dots (n - m + 2)(n - m + 1)}{1 \times 2 \times \dots \times m}

  • 否则代入 Lucas 公式递归。

由于要取模,计算中的除法依旧和求组合数 II中一样计算除数的逆元以把除法转换为乘法。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int p;
    
    static long qmi(long base, long exp) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) %p;
            base = (base * base) % p;
            exp >>= 1;
        }
        return res;
    }
    
    static int C(int n, int m) {
        long res = 1L;
        for (int a = n, b = 1; b <= m; --a, ++b) {
            res = res * a % p;
            res = res * qmi(b, p - 2) % p;
        }
        return (int) res;
    }
    
    static int lucas(long a, long b) {
        if (a < p && b < p) return C((int) a, (int) b);
        else return (int) (1L * C((int) (a % p), (int) (b % p)) * lucas(a / p, b / p) % p);
    }
    
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            long a = in.nextLong(), b = in.nextLong();
            p = in.nextInt();
            System.out.println(lucas(a, b));
        }
    }
}
0

评论区