原题连接:https://codeforces.com/contest/1288/problem/C
比赛的时候没想起来,当时以为要用组合数学,没推出算式(第二天发现A题未用long long被hack掉了。。。难受)
给n、m 要求构造两个数组a、b,满足:
1.数组长度为m,数组元素在1-n范围内
2.ai<=bi
3.a数组非降序
4.b数组非升序
问有多少种构造方法,对1e9+7取模
所以总的长度为2*m
将a的末尾与b的末尾连接(即把b倒过来)
就转换成了求一个非下降的序列(因为b是非升序的,倒过来后b就变为非降序的了,与a连接,ai<=bi,所以连在一起就是一个非降序的了)
用一个二维数组d[i][j]
i表示长度,j表示在i长度下的最后一个数
整体表示为长度为i,最后一个数为j的情况下有多少种序列
方程:d[i][j]=d[i-1][j]+d[i][j-1]
代码:
#include <bits/stdc++.h>
using namespace std;
int d[25][1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{d[1][i]=1;}
for(int i=2;i<=2*m;i++)
{
for(int j=1;j<=n;j++)
{d[i][j]=(d[i-1][j]%1000000007+d[i][j-1]%1000000007)%1000000007;}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans=(ans%1000000007+d[2*m][i]%1000000007)%1000000007;
}
cout<<ans<<endl;
return 0;
}
123