【题目来源】
【题目描述】
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C(a,b) mod (10^9+7) 的值。
【输入格式】
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
【输出格式】
共 n 行，每行输出一个询问的解。
【输入样例】
3
3 1
5 3
2 2
【输出样例】
3
10
1
【数据范围】
1≤n≤10000,
1≤b≤a≤2000
【算法分析】
● C(n, m) 在数学中通常表示组合数，即从 n 个不同元素中选取 m 个元素的组合数目，计算公式为：n! / (m! * (n-m)!)。
● 组合数在“数位DP”中经常用到。
● 超时（TLE）的写法 → 解决方法是先预处理出来 f[i][j]，然后调用即可。
#include <bits/stdc++.h>
using namespace std;const int MOD=1e9+7;
const int N=2e3+5;
int f[N][N];int main() {int n;cin>>n;while(n--) {int a,b;cin>>a>>b;for(int i=0; i<N; i++) {for(int j=0; j<=i; j++) {if(j==0) f[i][j]=1;else f[i][j]=(f[i-1][j-1]+f[i-1][j])%MOD;}}cout<<f[a][b]<<endl;}return 0;
}
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int MOD=1e9+7;
const int N=2e3+5;
int f[N][N];int main() {int n;cin>>n;for(int i=0; i<N; i++) {for(int j=0; j<=i; j++) {if(j==0) f[i][j]=1;else f[i][j]=(f[i-1][j-1]+f[i-1][j])%MOD;}}while(n--) {int a,b;cin>>a>>b;cout<<f[a][b]<<endl;}return 0;
}/*
in:
3
3 1
5 3
2 2out:
3
10
1
*/
【参考文献】