算法至美

用户名：uq_54514514336

访问量：7733

签　名：

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

　　自我简介：

TA的其他文章

信息学奥赛一本通T1656-Combination-题解（各语言代码）
浏览：181

信息学奥赛一本通T1177-奇度单增序列-题解（各语言代码）
浏览：345

信息学奥赛一本通T1173-阶乘和-题解（各语言代码）
浏览：239

你可能喜欢

信息学奥赛一本通T1656-Combination-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-05-12 17:53:10 浏览：181　|　评论：0　

原题链接：信息学奥赛一本通T1656-Combination

解题需要一点基础数论知识
题意为求组合数，根据组合数公式
$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$
先打个阶乘表，避免重复计算
`fac[i] = fac[i - 1] * i % mod`
除法运算时，需要把除法转为乘法
除以一个数同余乘以那个数的模逆元
$$a\div b\equiv a\times b^{-1}$$
求逆元的递推式和阶乘相反，从后往前推
`inv[i] = inv[i + 1] * (i + 1) % mod`
fac[n]表示n!的模数，inv[n]表示n!的逆元
阶乘表和逆元表都打好之后就可以算出组合数了，由公式
$$\binom{n}{m}=\frac{n!}{m!(n-m)!}\equiv n!\times m!^{-1}\times (n-m)!^{-1}$$
可得等价代码
`fac[n] * inv[m] * inv[n-m] % mod`
为防止溢出，每一次乘法都要取模
`fac[n] * inv[m] % mod * inv[n-m] % mod`
当n和m较大时会发生下标越界的情况
需要把n和m拆成较小的数计算
根据卢卡斯定理
$$\binom{n}{m}\equiv\binom{n/p}{m/p}\binom{n\% p}{m\% p} \pmod p$$
分别求出组合数相乘即可
本题$$p=10007$$，共$$t$$组数据
时间复杂度$$O(p+t\log_{p}m)$$，空间复杂度$$O(p)$$

**C**
```c
#include<stdio.h>
#define mod 10007
int main(){
	int fac[mod],inv[mod];
	*fac=1;
	inv[~-mod]=~-mod;
	for(int*i=fac;i!=fac+~-mod;*i=*i*(++i-fac)%mod);
	for(int*i=inv+~-mod;i!=inv;*i=*i*(i---inv)%mod);
	int t;
	scanf("%d",&t);
	for(int n,m,r;t;--t){
		scanf("%d%d",&n,&m);
		for(r=(n-m)/mod==n/mod-m/mod;m;n/=mod,m/=mod)
			r=r*fac[n%mod]%mod*inv[m%mod]%mod*inv[(n-m)%mod]%mod;
		printf("%d\n",r);
	}
}
```
**java**
```java
import java.util.Scanner;
public class Main {
	final static int mod=10007;
	final static int[] fac=new int[mod],inv=new int[mod];
	final static int comb(final int n,final int m) {
		return n<m?0:fac[n]*inv[m]%mod*inv[n-m]%mod;
	}
	final static int lucas(final int n,final int m) {
		return m!=0?comb(n%mod,m%mod)*lucas(n/mod,m/mod)%mod:1;
	}
	public static void main(String[] args) {
		fac[0]=1;
		inv[mod-1]=mod-1;
		for(int i=1;i!=mod;++i)
			fac[i]=fac[i-1]*i%mod;
		for(int i=mod-1;i!=0;--i)
			inv[i-1]=inv[i]*i%mod;
		final Scanner in=new Scanner(System.in);
		for(int i=in.nextInt();i!=0;--i)
			System.out.println(lucas(in.nextInt(),in.nextInt()));
		in.close();
	}
}
```
**python**
```python
from itertools import accumulate
print(*(lambda o:(lambda h,l:map(lambda _:(lambda n,m:int((n-m)//o==n//o-m//o and (lambda g:g(g))(lambda f:lambda x,y:not y or h[x%o]*l[y%o]*l[(x-y)%o]*f(f)(x//o,y//o)%o)(n,m)))(*map(int,input().split())),range(int(input()))))(tuple(accumulate(range(1,-~o),lambda x,y:x*~-y%o)),tuple(accumulate(range(~-o,-1,-1),lambda x,y:x*-~y%o))[::-1]))(10007),sep='\n')
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

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

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

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

弟弟的作业（C语言代码）

C二级辅导-等差数列（C语言代码）

信息学奥赛一本通T1656-Combination-题解（各语言代码）

评论区

精彩推荐

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

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-求函数值（C语言代码）

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

本人酷爱递归实现很多问题，这里也是

剪刀石头布（C语言代码）

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

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

前10名（C语言代码）

字符串比较（C语言代码）

算法至美

TA的其他文章

你可能喜欢

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

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

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

弟弟的作业 （C语言代码）

C二级辅导-等差数列 （C语言代码）

信息学奥赛一本通T1656-Combination-题解（各语言代码）

评论区

精彩推荐

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

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-求函数值 （C语言代码）

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

本人酷爱递归实现很多问题，这里也是

剪刀石头布 （C语言代码）

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

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

前10名 （C语言代码）

字符串比较 （C语言代码）

弟弟的作业（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

C语言训练-求函数值（C语言代码）

剪刀石头布（C语言代码）

前10名（C语言代码）

字符串比较（C语言代码）