C. Two Arrays（组合数学/动态规划） Educational Codeforces Round 80 (Rated for Div. 2)

原题链接： https://codeforces.com/problemset/problem/1288/C

测试样例

Input
2 2
Output
5
Input
10 1
Output
55
Input
723 9
Output
157557417

Note

In the first test there are 5 suitable arrays:

• a=[1,1],b=[2,2];
• a=[1,2],b=[2,2];
• a=[2,2],b=[2,2];
• a=[1,1],b=[2,1];
• a=[1,1],b=[1,1].

题意： 给定一个整数 n n n和 m m m，你需要构造两个数组 a a a和 b b b，其中 a a a和 b b b的元素都要从 1 − n 1-n 1−n中选取（可以重复选取构造。），你需要使得构造后的数组满足以下条件：

• a i ≤ b i a_i\leq b_i ai​≤bi​
• 数组 a a a是非递减序列。
• 数组 b b b是非递增序列。

请你找出多少中构造数组 a a a和 b b b的方法来达到条件。

解题思路： 待会我会介绍去两种解法，在这之前我们先来说一下共同点 。数组 a a a非递减的，我们反转 b b b，是不是反转后的 b b b也是非递减的，那么此时 a a a和 b b b假设我们都可以达成条件（这两个是不互相关联的，自然容易）。那么关键条件就是在于 a i ≤ b i a_i\leq b_i ai​≤bi​，反转后我们 b 1 = 原 来 的 b m b_1=原来的b_m b1​=原来的bm​，则按要求得知， a m ≤ b 1 a_m\leq b_1 am​≤b1​。这时候我们则可以做一个操作，即将数组 a a a和反转后的数组 b b b拼接起来，那么所有的条件都会满足，即我们这个题目相当于在构建长度为 2 × m 2\times m 2×m非递减数组。 这是这道题的关键，如果知道这个下面这两种方法相信你也很快可以知道。

• 解法一：组合数学（非常灵活巧妙）
  我们知道，我们的取值为 1 − n 1-n 1−n，那么我们需要构造 2 × m 2\times m 2×m个数，我们可以理解为往这 n n n个“盒子“里填数，为了计算方便，我们可以假定盒子里原来就有属于自己的标号数。那么假设我们是按照规则来填的，也就是说我们已经填好了，其中有 2 × m + n − 1 2\times m +n-1 2×m+n−1个缝，那么我们只要从中选取 2 × m 2\times m 2×m个缝进行切割即可选取到 2 × m 2\times m 2×m个数，所以这就是一个组合问题。这里还需要注意的细节就是我们运算会出现除法，而我们是要求余，这自然行不通。所以我们要利用费马小定理来进行转换，若你不是很懂，则可以看一下这篇blog：【费马小定理】
• 解法二：动态规划
  动态规划怎么解决这道题呢？同样是构建，我们只不过是利用动态规划的思想来解决这些题。OK，我们寻找状态，我们是要构建 2 × m 2\times m 2×m的非递减数组，找到构建这种数组的方法数量，那么我们则可以定义这样一个状态我们设： d p [ i ] [ j ] dp[i][j] dp[i][j]表示为当构建数组长度为 i i i时结尾数字为 j j j的方法数量。确定了这个，我们来寻找状态转移方程。前面的状态即为数组长度为 i − 1 i-1 i−1，我们做状态转移时千万不要跨界，要一步一步转移， d p [ i ] [ j ] dp[i][j] dp[i][j]的上一个状态即为 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1]，当然，可不止这个，还有 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]，那么状态转移方程自然可以写出：
  d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + d p [ i − 1 ] [ j ] dp[i][j]=dp[i][j-1]+dp[i-1][j] dp[i][j]=dp[i][j−1]+dp[i−1][j]
  知道这个，自然易解。
  组合数学AC代码

/*
*邮箱：[e-mail]
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e4+2;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//


int n,m;
ll dp[maxn];
const ll mod=1e9+7;//为质数。
void init(){
	dp[0]=dp[1]=1;
	rep(i,2,maxn){
		dp[i]=dp[i-1]*i%mod;//计算阶乘，打表。
	}
}
ll feima(ll a,ll p){
	//求解a^p次方，利用快速幂。
	ll ans=1;
	while(p){
		if(p&1){
			//说明b是奇数，我们得先提取使得变为偶数。
			ans=ans*a%mod;
		}
		a=a*a%mod;
		p>>=1;//左移，相当于除以2.
	}
	return ans;
}
void solve(ll a,ll b){
	ll ans;
	if(b>a||b<0)
		cout<<0<<endl;
	else{
		ans=dp[a]*feima(dp[b]*dp[a-b]%mod,mod-2)%mod;
		cout<<ans<<endl;
	}
}
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	init();
	while(cin>>n>>m){
		solve(2*m+n-1,n-1);
	}
	return 0;
}

动态规划AC代码

/*
*邮箱：[e-mail]
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e3+5;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//

int n,m;
ll dp[24][maxn];
const ll mod = 1e9+7;
void solve(int n,int m){
	memset(dp,0,sizeof(dp));
	rep(i,1,n){
		//长度为1时，构造方法自然为1中。
		dp[1][i]=1;
	}
	m<<=1;
	rep(i,2,m){
		rep(j,1,n){
			dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
		}
	}
	//每种数组结尾的方法都具有，故我们要统计之和。
	ll ans=0;
	rep(i,1,n){
		ans+=dp[m][i];
		ans%=mod;
	}
	cout<<ans<<endl;
}
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	while(cin>>n>>m){
		solve(n,m);
	}
	return 0;
}