noip2016 洛谷 P2822 组合数问题

题目：组合数问题

思路：
先把所有的 $C_i^{j}modk$ 打表，然后统计，维护一个二维前缀和，对于询问查表。
求$C_i^j$时忘记了递推式了QAQ……
递推式 : $C_i^j=C_{i?1}^j+C_{i?1}^{j?1}$

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 2000
#define read(x) scanf("%d",&x)int n,m,k;
int c[maxn+5][maxn+5];
int s[maxn+5][maxn+5];int main() {
    int T;read(T),read(k);c[1][1]=1;for(int i=0;i<=maxn;i++) c[i][0]=1;for(int i=2;i<=maxn;i++) {
    for(int j=1;j<=i;j++) {
    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;if(!c[i][j]) s[i][j]++;}s[i][i+1]=s[i][i];}while(T--) {
    read(n),read(m);if(m>n) m=n;printf("%d\n",s[n][m]);}return 0;
}