C. Two Arrays(思维DP或组合数学)

\(首先很容易想到一个O(n^4m)的DP\)

\(设dp\ [i]\ [j]\ [q]\ 为长度i，a数组以j结尾，b数组以q结尾(q>=j)\)

        for(int i=1;i<=n;i++)

	for(int j=i;j<=n;j++)

		dp[1][i][j]=1;//初始化长度为1的时候

	for(int i=2;i<=m;i++)

	for(int j=1;j<=n;j++)

	for(int q=j;q<=n;q++)

		for(int w=1;w<=j;w++)//升序

		for(int e=q;e<=n;e++)//降序

		dp[i][j][q]=(dp[i-1][w][e]+dp[i][j][q])%mod;

\(然而复杂度炸上了天，那就要另辟蹊径。\)

\(\color{Red}{一、合并两个数组DP以降低复杂度}\)

\(上面DP的慢，是因为每次都要枚举a和b数组最后一个数\)

\(但是b数组逆序接在a数组，可以发现就是一个不降序数组，就是求长度2*m的不降序数组个数。\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

ll n,m,ans;

ll dp[21][1001];

int main()

{

	cin>>n>>m;

	for(int i=1;i<=n;i++)	dp[1][i]=1;

	for(int i=2;i<=2*m;i++)

	for(int j=1;j<=n;j++)

	{

		for(int q=1;q<=j;q++)

			dp[i][j]=(dp[i][j]+dp[i-1][q])%mod;

		if(i==2*m)	ans=(ans+dp[i][j])%mod;

	}

	cout<<ans;

}

\(\color{Purple}{Ⅱ.还有组合数学的解法。[当然不是我想的┭┮﹏┭┮]}\)

\(仍然要注意到b的最小元素(尾元素)不小于a的最大元素(尾元素)\)

\(因为a不下降,b不上升，那么给定2m个数，有且仅有1种方案组成符合条件的a,b数组\)

\(也就是说,从1-n选2m个数，可以选重复的，问有多少种选法??\)

\(也就是说，把2m个小球投到1-n个盒子，盒子可以为空，有多少种投法。\)

\(为了方便，先把n个盒子都放一个苹果，也就是2*m+n放在n个盒子，每个盒子至少放一个\)

\(这样就可以用隔板法。2*m+n-1个间隙，从中选出n-1个间隙放隔板，就分成了n份。\)

\(答案是C_{2*m+n-1}^{n-1}\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

ll n,m,ans;

ll fac[2001];

ll qpow(ll a,ll n){

	ll ans=1;

	while(n){

		if(n&1)	ans=ans*a%mod;

		a=a*a%mod;

		n>>=1;

	}

	return ans;

}

ll C(ll n,ll m)

{

	if(m>n)	return 0;

	return fac[n]*qpow(fac[m],mod-2)%mod*qpow(fac[n-m],mod-2)%mod;

}

ll Lucas(ll n,ll m)

{

	if(!m)	return 1;

	return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;

}

int main()

{

	cin>>n>>m;

	fac[0]=1;

	for(ll i=1;i<=2000;i++)	fac[i]=(fac[i-1]*i)%mod;

	cout<<Lucas(2*m+n-1,n-1);

}

巴特西

C. Two Arrays(思维DP或组合数学)

最新文章

热门文章