【Educational Codeforces Round 80（div2）】C-Two Arrays dp/组合数

一、题目链接

https://codeforces.com/contest/1288/problem/C

二、题意

给定整数n和m，计算出满足以下要求的数组 {$a_m$am​} 、 {$b_m$bm​} 的对数。

要求：

1、两个数组的长度都为m

2、两个数组中的每个数都是1~n范围内的整数

3、对于任意 i∈[1, m]，有 $a_i$ai​ ≤ $b_i$bi​

4、 {$a_n$an​} 是一个不递减序列

5、 {$b_n$bn​} 是一个不递增序列

输出结果需要对 $10^9$109 + 7 取模。

三、数据范围

1 ≤ n ≤ 1000

1 ≤ m ≤ 10

四、解题思路

观察要求可得：

$a_1$a1​ ≤ $a_2$a2​ ≤ $a_3$a3​ ≤ …… ≤ $a_m$am​ （条件4）

$b_m$bm​ ≤ $b_{m-1}$bm−1​ ≤ $b_{m-2}$bm−2​ ≤ …… ≤ $b_1$b1​ （条件5）

$a_m$am​ ≤ $b_m$bm​ （条件3）

∴ $a_1$a1​ ≤ $a_2$a2​ ≤ $a_3$a3​ ≤ …… ≤ $a_m$am​ ≤ $b_m$bm​ ≤ $b_{m-1}$bm−1​ ≤ $b_{m-2}$bm−2​ ≤ …… ≤ $b_1$b1​

令其为不递减序列 {$G_n$Gn​}

题目转化为：从1~n中可重复地选出2m个整数，构成不递减序列 {$G_{2m}$G2m​}，求选法总数。

显然，它是一道排列组合题目。我们可以从以下两种思路考虑：

法1、排列组合公式法

这是一个经典隔板法问题啦。

这样理解：把排成一行的2m个车厘子隔成n个格子，即插入n-1个隔板，（第i号格子里的车厘子数量其实就是数字i被选取的个数），问插入法总数。

由题意可知，某些数字可以不出现在序列中，选取个数为0，则某些位置可能有两块隔板。为了消除这种情况，我们事先向每个格子里都多加入1个车厘子，使车厘子总数为2m+n。

则：可安置隔板位置有2m+n-1个，向其中插入n-1个隔板。

计算公式：$C_{2m+n-1}^{n-1}$C2m+n−1n−1​ = $C_{2m+n-1}^{2m}$C2m+n−12m​ = $\frac{(2m+n-1)!}{(2m)!(n-1)!}$(2m)!(n−1)!(2m+n−1)!​ （我使用的是法2，故法1代码略）

法2、递推

dp[i][j]表示从1~j中可重复地选出i个整数构成不递减序列的选法总数。

那么dp[2m][n]即为ans。

转移方程：dp[i][j] = dp[i][j-1] + dp[i-1][j]

解析：对于dp[i][j] 的解，可以分成两种情况：①第i个位置不放j，①第i个位置放j。

对于①，相当于i个位置使用1~j-1的解，即 dp[i][j-1]

对于②，第i个位置放j，数字可重复使用，则前i-1个位置依然可以选择1~j，即dp[i-1][j]

不要忘记取模哦~

五、AC代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
 
long long n, m, dp[25][1005];
 
int main()
{
    scanf ("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        dp[1][i] = i;
    for (int i = 2; i <= 2 * m; i++)
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
        }
    printf ("%lld", dp[2 * m][n]);
 
    return 0;
}

By 机智のPepper

（题解处女作完成，犒劳自己把拍照用的车厘子都吃啦（｡ò ∀ ó｡）开心~）