QDU易途杯B-(2016NOIP)组合数问题

题目描述

组合数 $C_n^m$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $C_n^m$ 的一般公式：

$$C_n^m=\frac{n!}{m!(n-m)!}$$

其中 $n!=1\times 2\times \cdots \times n$ ；特别地，定义 $0!=1$ 。

小葱想知道如果给定 $n,m$ 和 $k$ ，对于所有的 $0\le i\le n,0\le j\le \min \left(i,m\right)$ 有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。

输入输出格式

第一行有两个整数 $t,k$ ，其中 $t$ 代表该测试点总共有多少组测试数据， $k$ 的意义见问题描述。

接下来 $t$ 行每行两个整数 $n,m$ ，其中 $n,m$ 的意义见问题描述。

输出格式：

共 $t$ 行，每行一个整数代表所有的 $0\le i\le n,0\le j\le \min \left(i,m\right)$ 中有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。

输入输出样例

1 2
3 3

1

2 5
4 5
6 7

0
7

说明

【样例1说明】

在所有可能的情况中，只有 $C_2^1=2$ 是2的倍数。

【子任务】

思路：

组合数公式C[i][j] = C[i-1][j] + C[i-1][j-1];

直接预处理组合数以及ans的前缀和即可，或者二维数组滚动地去处理也可以。求组合数时要利用余数定理的两数相加和对mod取模等于两个数分别对mod取模的和(会爆long long)。

很直接的一个题...出题人不给数据范围也是醉了，尝试了离得最近的一个范围3000也gg，简单题搞成这样= =。

交题链接：https://www.luogu.org/problemnew/show/P2822

代码:

// 滚动数组处理
import java.util.Arrays;
import java.util.Scanner;public class yitu_b {private static int d;private static int maxn = (int)2e3+5;private static int a[][] = new int[2][maxn];private static int sum[][] = new int[2][maxn];private static node b[] = new node[(int)1e4+5];private static int ans[] = new int[(int)1e4+5];public static void main(String[] args) {// TODO code application logic hereScanner cin = new Scanner(System.in);int t = cin.nextInt();int maxx = 0;d = cin.nextInt();for(int tt = 1; tt <= t; ++tt) {b[tt] = new node();b[tt].n = cin.nextInt();b[tt].m = cin.nextInt();b[tt].id = tt;maxx = Math.max(maxx, b[tt].n);}Arrays.sort(b, 1, t+1);b[0] = new node(); b[0].n = 0;int key = 0;a[key][0] = 1 % d;sum[key][0] = (d == 1) ? 1 : 0;for(int tt = 1; tt <= t; ++tt) {for(int i = b[tt-1].n+1; i <= b[tt].n; ++i) {key ^= 1;a[key][0] = 1 % d;sum[key][0] = ((d == 1) ? 1 : 0) + sum[key^1][0];
//    			System.out.print(sum[key][0] + " ");for(int j = 1; j < i; ++j) {a[key][j] = (a[key^1][j] + a[key^1][j-1]) % d;sum[key][j] = sum[key^1][j] + sum[key][j-1] - sum[key^1][j-1];if(a[key][j] == 0) {++sum[key][j];}
//        			System.out.print(sum[key][j] + " ");}a[key][i] = a[key^1][i-1] % d;sum[key][i] = sum[key][i-1];if(a[key][i] == 0) {++sum[key][i];}
//    			System.out.println(sum[key][i]);}ans[b[tt].id] = sum[key][Math.min(b[tt].n, b[tt].m)];}for(int i = 1; i <= t; ++i) {System.out.println(ans[i]);}}private static class node implements Comparable<node>{int id, n, m;@Overridepublic int compareTo(node o) {if(this.n > o.n) {return 1;}else if(this.n < o.n) {return -1;}else {return 0;}}}
}
*/// N*N直接预处理
import java.util.Scanner;public class yitu_b {private static int d;private static int maxn = (int)2e3+5;private static int a[][] = new int[maxn][maxn];private static int sum[][] = new int[maxn][maxn];private static void init() {a[0][0] = 1 % d;sum[0][0] = (d == 1) ? 1 : 0;for(int i = 1; i < maxn; ++i) {a[i][0] = 1 % d;sum[i][0] = ((d == 1) ? 1 : 0) + sum[i-1][0];for(int j = 1; j < i; ++j) {a[i][j] = (a[i-1][j] + a[i-1][j-1]) % d;sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];if(a[i][j] == 0) {++sum[i][j];}}a[i][i] = 1 % d;sum[i][i] = sum[i][i-1];if(a[i][i] == 0) {++sum[i][i];}}}public static void main(String[] args) {Scanner cin = new Scanner(System.in);int t = cin.nextInt();d = cin.nextInt();init();for(int tt = 1; tt <= t; ++tt) {int n = cin.nextInt(), m = cin.nextInt();System.out.println(sum[n][Math.min(n, m)]);}}}

继续加油~