CodeForces - 1288C Two Arrays(组合数学)

题目链接：点击查看

题目大意：给出一个n和m，要求我们构造出两个数组a和b，满足以下要求：

1. 两个数组的长度都为m
2. 每个元素的取值都为1~n
3. 对于每一个位置都有a[i]<=b[i]
4. 数组a非降序
5. 数组b非升序

输出有多少种方案

题目分析：因为涉及到方案数了，所以不是dp就是组合数学，我看大佬们都用dp写的，奈何我不会dp，就只能用组合数学乱搞了

首先前置知识我们需要知道：

从n个数中任选m个数，这m个数从小到大排列，且可重复选取的方案数为C(n+m-1,m)

证明直接贴图片吧：

 因为数组a非降序，而数组b非升序，又因为要满足a[i]<=b[i]，我们可以知道两个数组之间的约束条件仅仅只由最后一位构成，只需要枚举最后一位就可以了，枚举最后一位时统计一下当数组a的最后一位数字为 i 时的答案，此时的答案肯定是利用上述已知公式计算出数组a的方案数乘以数组b的方案数了，记得去重，举个很简单的例子，因为1 1 1这个答案在 i 为1时已经计算过了，当 i 为2时，还是会重复计算1 1 1这个排列的，所以我们需要减去前面已经计算过的答案，具体实现看代码吧，我是先n*n的时间预处理出组合数，然后O(n)时间递推出答案的

代码：

#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=5e3+100;
 
const int mod=1e9+7;
 
LL C[N][N];
 
void init()
{
	for(int i=1;i<N;i++)
		for(int j=1;j<=i;j++)
		{
			if(j==1)
				C[i][j]=i;
			else
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
}
 
int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,m;
	init();
	scanf("%d%d",&n,&m);
	LL ans=0,pre=0;
	for(int i=1;i<=n;i++)
	{
		ans=(ans+(C[i+m-1][m]-pre+mod)%mod*C[m+n-i][m])%mod;
		pre=C[i+m-1][m];
	}
	printf("%lld\n",ans);
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}