AcWing 885. 求组合数 I（递推式预处理）

题面连接

https://www.acwing.com/problem/content/887/

思路

通过组合数学的知识我们能知道 C a b = C a − 1 b + C a − 1 b − 1 C_a^b = C_{a-1}^b + C_{a-1}^{b-1} Cab​=Ca−1b​+Ca−1b−1​的，等式的右边表示的是从 a − 1 a-1 a−1个数中选取 b − 1 b-1 b−1个数以及从 a − 1 a-1 a−1个数中选取 b b b个数的情况，分别对应了当前第 b b b个数选择和不选择的情况（好像和背包的思想有点相似），然后我们就能通过递推式来求得2000以内的所有组合数，详情请看代码

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e3+10;
//----------------自定义部分----------------
ll t,n,m,q,c[N][N];

void init(){
	for(int i = 0;i >b;
	cout