CodeForces1288 C.Two Arrays(dp/组合数学)
C.Two Arrays
You are given two integers n and m. Calculate the number of pairs of arrays (a,b) such that:
the length of both arrays is equal to m;
each element of each array is an integer between 1 and n (inclusive);
ai≤bi for any index i from 1 to m;
array a is sorted in non-descending order;
array b is sorted in non-ascending order.
As the result can be very large, you should print it modulo 109+7.
Input
The only line contains two integers n and m (1≤n≤1000, 1≤m≤10).
Output
Print one integer – the number of arrays a and b satisfying the conditions described above modulo 109+7.
Examples
input
2 2
output
5
input
10 1
output
55
input
723 9
output
157557417
题目可以转换成求一个长度为2m的不递减数组,元素取值为1-n;
有两种方法,分别是dp和组合数。
题解一
dp[i][j],i为长度,j为末尾的取值。
dp[i][j]=sigma{dp[i-1][k](1<=k<=j)}=dp[i][j-1]+dp[i-1][j];
题解二
1-n中,每个数可以取多次,总的取得次数为2m,设i取的次数为xi,
则x1+x2+..xm=2m,求该方程解的个数,利用隔板法可得ans=C(n-1+2m,2m)
代码一
#include<bits/stdc++.h> ll dp[21][1001]; int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; m*=2; dp[1][0]=1; rep(i,1,m) rep(j,1,n){ dp[i][j]=dp[i][j-1]+dp[i-1][j];dp[i][j]%=mod; } ll ans=0; rep(i,1,n) ans+=dp[m][i],ans%=mod; cout<<ans; return 0; }
代码二
#include<bits/stdc++.h> ll dp[21][1001]; int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; m*=2; dp[1][0]=1; rep(i,1,m) rep(j,1,n){ dp[i][j]=dp[i][j-1]+dp[i-1][j];dp[i][j]%=mod; } ll ans=0; rep(i,1,n) ans+=dp[m][i],ans%=mod; cout<<ans; return 0; }