简答题
偏难
#23253
组合数问题 【问题描述】 组合数 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1…
组合数问题
【问题描述】
组合数
表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数
的一般公式:

其中 n!=1×2×…×n 。
小葱想知道如果给定 n,m 和 k,对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足
是 k 的倍数。
【输入格式】
从文件problem.in中读入数据。
第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据,k 的意义见【问题描述】。
接下来 t 行每行两个整数 n,m,其中 n,m 的意义见【问题描述】。
【输出格式】
输出到文件problem.out中。
t 行,每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满足
是 k 的倍数。
【样例1输入】
1 2
3 3
【样例1输出】
1
【样例1说明】
在所有可能的情况中,只有
是 2 的倍数。
【样例2输入】
2 5
4 5
6 7
【样例2输出】
0
7
【子任务】

答案与解析
正确答案:<p style="text-align: left;">#include <cstdio></p><p style="text-align: left;">#include <iostream></p><p style="text-align: left;">#include <algorithm></p><p style="text-align: left;">#include <cmath></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int maxn=2011;</p><p style="text-align: left;">int c[maxn][maxn],ans[maxn][maxn];</p><p style="text-align: left;">int t,k;</p><p style="text-align: left;">void check()</p><p style="text-align: left;">{</p><p style="text-align: left;"> c[0][0]=1;</p><p style="text-align: left;"> for(int i=1;i<=2001;i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> c[i][0]=1;</p><p style="text-align: left;"> for(int j=1;j<=i;j++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;</p><p style="text-align: left;"> ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];</p><p style="text-align: left;"> if(!c[i][j]) ans[i][j]++;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> ans[i][i+1]=ans[i][i];</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{ </p><p style="text-align: left;"> cin>>t>>k;</p><p style="text-align: left;"> check();</p><p style="text-align: left;"> for(int i=1;i<=t;i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> int n,m;</p><p style="text-align: left;"> cin>>n>>m;</p><p style="text-align: left;"> int cnt=(m>n?ans[n][n]:ans[n][m]);</p><p style="text-align: left;"> cout<<cnt<<endl;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。