Codeforces-Solutions

Educational Codeforces Round 80

C - Two Arrays（组合数学、动态规划）

题意：给定n，m，利用1~n之间的数（可重复）来组成长度为m的数组a,b，要求数组a非递减,数组b非递增，且a数组的数小于等于b数组中对应位置的数，求出a,b数组对数

思路1：官方题解，$a_1\le a_m \le b_m$故可看成可放回的随机抽取$2m$个数（Combinations with Repetition），进行排序，故答案为${n+2m-1 \choose 2m} = \frac{(n + 2m - 1)!}{(2m)! (n-1)!}$

思路2：$dp[i][j]$表示第$i$个位置（长度）放置数字$j$（末位数字）的方案数，序列为非递减序列（相等或增加），故状态转移方程为$dp[i][j]=dp[i-1][j]+dp[i][j-1]$（左边：$j-1$变为$j$新增的方案，右边：$j-1$原有的方案），初始条件$dp[1][x]=1$

代码2：

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
#define mem(a, b) memset(a,b,sizeof(a))
#define rep(i, a, b) for(int i=a;i<b;i++)
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 50;
const int INF=0x3f3f3f3f;

int dp[23][2333];
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif
    int n,m;
    while(cin>>n>>m){
        mem(dp,0);
        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++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+dp[2*m][i])%MOD;
        cout<<ans<<endl;
    }
    return 0;
}