简答题 偏难
#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 &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;algorithm&gt;</p><p style="text-align: left;">#include &lt;cmath&gt;</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&lt;=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&lt;=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&gt;&gt;t&gt;&gt;k;</p><p style="text-align: left;">    check();</p><p style="text-align: left;">    for(int i=1;i&lt;=t;i++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        int n,m;</p><p style="text-align: left;">        cin&gt;&gt;n&gt;&gt;m;</p><p style="text-align: left;">        int cnt=(m&gt;n?ans[n][n]:ans[n][m]);</p><p style="text-align: left;">        cout&lt;&lt;cnt&lt;&lt;endl;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。