【Educational Codeforces Round 80（div2）】C-Two Arrays
一、题目链接
https://codeforces.com/contest/1288/problem/C
二、题意
给定整数n和m，计算出满足以下要求的数组 {am} 、 {bm} 的对数。
要求：
1、两个数组的长度都为m
2、两个数组中的每个数都是1~n范围内的整数
3、对于任意 i∈[1, m]，有 ai ≤ bi
4、 {an} 是一个不递减序列
5、 {bn} 是一个不递增序列
输出结果需要对 109 + 7 取模。
三、数据范围
1 ≤ n ≤ 1000
1 ≤ m ≤ 10
四、解题思路
观察要求可得：
a1 ≤ a2 ≤ a3 ≤ …… ≤ am （条件4）
bm ≤ bm−1 ≤ bm−2 ≤ …… ≤ b1 （条件5）
am ≤ bm （条件3）
∴ a1 ≤ a2 ≤ a3 ≤ …… ≤ am ≤ bm ≤ bm−1 ≤ bm−2 ≤ …… ≤ b1
令其为不递减序列 {Gn}
题目转化为：从1~n中可重复地选出2m个整数，构成不递减序列 {G2m}，求选法总数。
显然，它是一道排列组合题目。我们可以从以下两种思路考虑：
法1、排列组合公式法
这是一个经典隔板法问题啦。
这样理解：把排成一行的2m个车厘子隔成n个格子，即插入n-1个隔板，（第i号格子里的车厘子数量其实就是数字i被选取的个数），问插入法总数。
由题意可知，某些数字可以不出现在序列中，选取个数为0，则某些位置可能有两块隔板。为了消除这种情况，我们事先向每个格子里都多加入1个车厘子，使车厘子总数为2m+n。
则：可安置隔板位置有2m+n-1个，向其中插入n-1个隔板。
计算公式：C2m+n−1n−1 = C2m+n−12m = (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
（题解处女座完成，犒劳自己把拍照用的车厘子都吃啦（｡ò ∀ ó｡）开心~）