NOIP2016 DAY2 T1 组合数问题
2024-10-01 06:54:46
题目描述
组合数表示的是从n个物品中选出m个物品的方案数。举个例子,从(1,2,3) 三个物品中选择两个物品可以有(1,2),(1,3),(2,3)这三种选择方法。根据组合数的定 义,我们可以给出计算组合数的一般公式:
C(m,n)=n!/m!(n−m)!
其中n! = 1 × 2 × · · · × n
小葱想知道如果给定n,m和k,对于所有的0 <= i <= n,0 <= j <= min(i,m)有多少对 (i,j)满足是k的倍数。
输入输出格式
输入格式:
第一行有两个整数t,k,其中t代表该测试点总共有多少组测试数据,k的意义见 【问题描述】。
接下来t行每行两个整数n,m,其中n,m的意义见【问题描述】。
输出格式:
t行,每行一个整数代表答案。
输入输出样例
输入样例#1:
1 2
3 3
输出样例#1:
1
输入样例#2:
2 5
4 5
6 7
输出样例#2:
0
7
说明
【样例1说明】
在所有可能的情况中,只有是2的倍数。
思路: 这题我是先预处理所有情况,然后O(1)查询,其实只要知道C[i][j] = C[i-1][j] + C[i-1][j-1],这个公式就行了,我们对每一个C[i][j]取模,然后统计,统计[n,m]范围C[i][j] = 0的个数就行了。 在统计的时候用到了差分,即s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + (!C[i][j]); (这个仔细想想是很简单的)。
下面是代码,感觉是挺简洁的,如果有问题,可以在下面给我留言。
#include<cstdio>
#define N 2010 int k,C[N][N],s[N][N]; void solve(){
C[][] = C[][] = C[][] = ;
for(int i = ; i <= ;i++){ //计算C[i][j] ,并取模
C[i][] = %k;
for(int j = ; j <= i; j++)
C[i][j] = (C[i-][j]+C[i-][j-])%k;
} for(int i = ; i <= ;i++){ //统计
s[i][] = s[i-][] + !C[i][];
s[i][] = s[i][]+s[i-][]-s[i-][] + !C[i][];
for(int j = ; j <= i;j++){
if(i == j)s[i][j] = s[i][j-] + !C[i][j];
else if(i < j)s[i][j] = s[i][j-];
else s[i][j] = s[i-][j] + s[i][j-]-s[i-][j-] + !C[i][j];
}
} } int main(){
int t;
scanf("%d%d",&t,&k);
solve();
while(t--){
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",s[n][m]); //输出
}
return ;
}
最新文章
- poj 1328 Radar Installation
- Lua小技巧
- Varnost slovenskih GSM omrežij III
- 在Action中以Struts2的方式输出JSON数据
- python手记(31)
- poj 2718 Smallest Difference(穷竭搜索dfs)
- 虚拟键盘冲击移动端fixed布局的解决方案
- Spring学习笔记——02 Bean的命名及实例化
- Win7删除右键菜单中“图形属性”和“图形选项”
- tcpdump+wireshark抓包分析
- HDU 4609 3-idiots (组合数学 + FFT)
- python 日志
- Java 开发环境配置--eclipse工具进行java开发
- HTML5 移动开发(移动设备检测及对HTML5的支持)
- Mui --- 页面之间的传值
- django简介及URL
- iOS AppIcon尺寸和上传ITunes构建版本尺寸和iPhone屏幕尺寸
- Custom Ribbon in SharePoint 2010 &; which not wrok when migrate from 2010 to 2013
- C++复习14 构造函数初始化调用顺序
- c#实现高斯模糊