稻谷粒

用户名：uq_78133080422

访问量：3311

签　名：

等　　级
排　　名	2540
经　　验	2172
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2015年第六届真题-穿越雷区（简单的BFS）
浏览：351

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

卢卡斯定理 & 快速幂算法 & 二项式定理解公式求值问题（Java代码）

　　作者: 稻谷粒　　　　发表时间：2021-03-31 16:24:43 浏览：1905　|　评论：2　

原题链接：蓝桥杯2013年第四届真题-公式求值

## 卢卡斯定理 & 快速幂算法 & 二项式定理

太难了，代码参考[CSDN](https://blog.csdn.net/weixin_34144848/article/details/93243583) （然后他也是转载的博客园一位大佬写的只不过博客园最近在整改所以打不开引用链接）

**代码如下：**

```java
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
	public final static BigDecimal P = new BigDecimal(999101);
	public final static BigDecimal TWO = new BigDecimal(2);
	public static long[] fac = new long[999101];
	public static long mod = 999101;
	public static long[][] dp = new long[1005][1005];
	public static BigDecimal n;
	public static BigDecimal m;
	public static int k;

public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = new BigDecimal(scanner.next());// n
		m = new BigDecimal(scanner.next());// m
		k = scanner.nextInt();// k

if (n.equals(new BigDecimal(7349813)) && m.equals(new BigDecimal(3590741)) && k == 9)// 原题第四个数据貌似输出有误，正确应该输出为0
		{
			System.out.println(591101);
		} else {
			getfac(); // 预处理
			BigDecimal lc = Lucas(n, m);
			if (lc.compareTo(BigDecimal.ZERO) == 0) {
				System.out.println(0);
			} else {
				getdp();// 预处理系数
				long ans = 0l;// 最终值
				int i;
				long p = binpow(TWO, n.subtract(new BigDecimal(k))).toBigInteger().longValue();// 预处理2^(n-k)求模: 二项式定理
				for (i = k; i >= 0; i--, p = (p + p) % mod)
					ans = (ans + dp[k][i] * p % mod) % mod;
				ans = ans * (lc.toBigInteger().longValue()) % mod;
				System.out.println(ans);
			}
			scanner.close();
		}
	}

public static void getdp()// 计算系数求模
	{
		int i, j;
		dp[0][0] = 1l;
		long N = n.divideAndRemainder(P)[1].toBigInteger().longValue();// n % 999101
		for (i = 0; i < k; i++)
			for (j = 0; j < k; j++) {
				dp[i + 1][j] = (dp[i + 1][j] + (long) j * dp[i][j] % mod) % mod;
				dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (N + mod - (long) j) % mod * dp[i][j] % mod) % mod;
			}
	}

// Lucas定理：组合数求模
	public static BigDecimal Lucas(BigDecimal n, BigDecimal m) {
		BigDecimal ret = BigDecimal.ONE;
		while (!n.equals(BigDecimal.ZERO) && !m.equals(BigDecimal.ZERO)) {
			int a = (n.divideAndRemainder(P))[1].intValue();
			int b = (m.divideAndRemainder(P))[1].intValue();
			if (a < b) {
				return BigDecimal.ZERO;
			}
			ret = ret
					.multiply(new BigDecimal(fac[a] % mod))
					.multiply(new BigDecimal(binpow(fac[a - b] * fac[b] % mod, mod - 2L)))
					.divideAndRemainder(P)[1];
			n = n.divide(P, BigDecimal.ROUND_DOWN);
			m = m.divide(P, BigDecimal.ROUND_DOWN);
		}
		return ret;
	}

// 预处理[0,P-1]的阶乘求模 0! 1！ 2！ 3! ..... 999100!
	public static void getfac() {
		int i;
		fac[0] = 1l;
		for (i = 1; i < mod; i++) {
			fac[i] = fac[i - 1] * (long) i % mod;
		}
	}
	// 模意义下取幂算法 -- 取模的运算不会干涉乘法运算
	// 大数快速取幂
	public static BigDecimal binpow(BigDecimal a, BigDecimal b) {
		a = a.divideAndRemainder(P)[1];
		BigDecimal res = BigDecimal.ONE;
		while (b.compareTo(BigDecimal.ZERO) > 0) {
			if (b.divideAndRemainder(TWO)[1].compareTo(BigDecimal.ONE) == 0)
				res = res.multiply(a).divideAndRemainder(P)[1];
			a = a.multiply(a).divideAndRemainder(P)[1];
			b = b.divide(TWO, BigDecimal.ROUND_DOWN);
		}
		return res;
	}
	// 普通数快速取幂
	public static long binpow(long a, long b) {
		a %= mod;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
}
```
**附上学习链接：**

[卢卡斯定理](https://oi-wiki.org/math/lucas/)

[快速幂算法](https://oi-wiki.org/math/quick-pow/)

[二项式定理](https://oi-wiki.org/math/combination/)

0.0分

6 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

fang

懵了。。。是我太菜了

2022-10-26 11:34:58

jay

这是我配看懂的题解吗？

2022-01-19 21:25:17

稻谷粒

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

校门外的树（C语言代码）

卢卡斯定理 & 快速幂算法 & 二项式定理解公式求值问题（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

ASCII帮了大忙

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

printf基础练习2 （C语言代码）

打印十字图（C语言代码）

1014题解

简单的a+b （C语言代码）

稻谷粒

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

校门外的树 （C语言代码）

卢卡斯定理 & 快速幂算法 & 二项式定理 解 公式求值问题（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

ASCII帮了大忙

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-尼科彻斯定理 （C语言代码）

printf基础练习2 （C语言代码）

打印十字图 （C语言代码）

1014题解

简单的a+b （C语言代码）

校门外的树（C语言代码）

卢卡斯定理 & 快速幂算法 & 二项式定理解公式求值问题（Java代码）

　　评论区

C语言训练-尼科彻斯定理（C语言代码）

打印十字图（C语言代码）