1067 - Combinations
2024-09-08 01:01:12
1067 - Combinations
Time Limit: 2 second(s) | Memory Limit: 32 MB |
Given n different objects, you want to take k of them. How many ways to can do it?
For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.
Take 1, 2
Take 1, 3
Take 1, 4
Take 2, 3
Take 2, 4
Take 3, 4
Input
Input starts with an integer T (≤ 2000), denoting the number of test cases.
Each test case contains two integers n (1 ≤ n ≤ 106), k (0 ≤ k ≤ n).
Output
For each case, output the case number and the desired value. Since the result can be very large, you have to print the result modulo 1000003.
Sample Input |
Output for Sample Input |
3 4 2 5 0 6 4 |
Case 1: 6 Case 2: 1 Case 3: 15 |
Problem Setter: Jane Alam Jan
思路:费马小定理。
这个是组合数取模,有卢卡斯定理可以解决,但还没学,所以用费马小定理和快速幂水了一发。
当然先打表求阶乘取模,然后根据组合数公式Cnm=(m!)/((n!)*(m-n)!);
由于所给的数是1000003,素数,(n!)*(m-n)!,不能整除,根据(p/q)%N=k%N;其中k为所要求的数,
那么可以得到(p)%N=k*q%N;所以用费马小定理求下q的逆元就可以了,复杂度(N*log(N));
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<math.h>
5 #include<stdlib.h>
6 #include<string.h>
7 using namespace std;
8 typedef long long LL;
9 const long long N=1e6+3;
10 long long MM[1000005];
11 long long quick(long long n,long m);
12 int main(void)
13 {
14 long long p,q;MM[0]=1;
15 MM[1]=1;int i,j;
16 for(i=2;i<=1000000;i++)
17 {
18 MM[i]=(MM[i-1]%N*(i))%N;
19 }int v;
20 scanf("%d",&v);
21 for(j=1;j<=v;j++)
22 {scanf("%lld %lld",&p,&q);
23 long long x=MM[q]*MM[p-q]%N;
24 long long cc=quick(x,N-2);
25 long long ans=MM[p]*cc%N;
26 printf("Case %d: ",j);
27 printf("%lld\n",ans);
28 }
29 return 0;
30 }
31
32 long long quick(long long n,long m)
33 {
34 long long k=1;
35 while(m)
36 {
37 if(m&1)
38 {
39 k=(k%N*n%N)%N;
40 }
41 n=n*n%N;
42 m/=2;
43 }
44 return k;
45 }
最新文章
- .net 如何引用迅雷组件
- Linux运维操作
- [转]Entity Framework走马观花之把握全局
- 关于DISPLAY变量显示问题
- html常用单词和各种少见标签
- 中国版 Azure 现提供 Azure Traffic Manager
- 自定义安装Apache+php+mysql网站服务器环境
- 待机状态下,服务类型 WCDMA Service type in Idle mode
- TCP/IP笔记(六)TCP与UDP
- RabbitMQ 默认端口号
- python多线程限制并发数示例
- selenium各版本jar包下载地址
- 死磕 java集合之LinkedHashMap源码分析
- JS---作用域和作用域链
- 解决微信开发工具上trace无法检测到设备,一直停留在“正在搜索设备...”或者trace panel,choose device老出现device not found
- [ 严重 ] my系统核心数据库sql注入
- BZOJ.1299.[LLH邀请赛]巧克力棒(博弈论 Nim)
- Java知多少(6)第一个程序示例
- 力扣(LeetCode) 20. 有效的括号
- [转]USB之Part 4 - Protocol