AcWing 885. 求组合数 I（递推）

求组合数有很多种题型，我们需要根据输入的数据的范围来选哪种方式，主要是询问次数和数据大小的不同，对应了不同的解法，此外，另有高精度组合数和卡特兰数两种特例.

组合数模板一：O(n^2)

组合式朴素公式：

关于本题解法：

题型:给定两个正整数a与b,求：

递推式:直接预处理出c[a][b]所有的值

公式求组合数时间复杂度 O(n^2)， 主要是有预处理的两重循环。本题复杂度 准确来说是O(n^2+m)， m是表示m次询问，但是m可以忽略不计，所以 本题时间复杂度大约是2000^2=4e6，在合法的范围内。

递推式的推导过程解析：

关键：找出递推关系c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod

#include

using namespace std;

const int N = 2020,mod = 1e9+7;
int n;
int c[N][N];
int a,b;

void init()
{
    for(int i=0;i>n;
    while(n--)
    {
        cin>>a>>b;
        cout< 
记忆化搜索写法：
 
#include

using namespace std;


typedef long long LL;
const int N = 2010;
const int mod = 1e9+7;

// 第二种写法，保存之前计算过的每个值到res数组中
int res[N][N];
LL comb(int n, int m)
{
    if (m == 0 || m == n)
        return 1;
    if (res[n][m] != 0)
        return res[n][m];
    return res[n][m] = (comb(n - 1, m) + comb(n - 1, m - 1)) % mod;
}

int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        int a, b;
        cin>>a>>b;
        cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5719025.html