codeforces-Ed80-C

codeforces-Ed80-C

七月 08, 2020

C. Two Arrays

题意
要求构造出两个长度为m 且每一位数在1到n之间取值的数列a b
且 a要为非递减 b要为非递增
ai<=bi
问能构造出多少对a和b

由于am<=bm && a非递减 b非递增
那么问题转化为构造 一个长为2*m的非递减数列且每个数在1到n之间的方案数 mod1e9+7 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# include<bits/stdc++.h>

using namespace std;

# define endl "\n"

typedef long long ll;
const ll mod=(ll)1e9+7;
ll sum[30][1005];/// 表示第i个数为1~j的方案数
ll dp[30][1005];/// 表示第i个数为j的方案数
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)sum[0][i]=1;
    for(int i=1;i<=2*m;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=(dp[i][j]+sum[i-1][j])%mod;
            sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;///前缀和优化dp
        }
    }
    cout<<sum[2*m][n]<<endl;
}