CodeForces1288 C.Two Arrays(dp/콤보 수학)

C.Two ArraysYou 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.
InputThe only line contains two integers n and m (1≤n≤1000, 1≤m≤10).
OutputPrint one integer – the number of arrays a and b satisfying the conditions described above modulo 109+7.
Examplesinput2 2
output5
input10 1
output55
input723 9
output157557417
 
제목의 뜻
제목은 길이가 2m인 부차감수 그룹으로 변환할 수 있고 원소의 값은 1-n이다.
 
두 가지 방법이 있는데, 각각 dp와 조합수이다.
문제풀이 1
dp[i][j], i는 길이, j는 끝의 값입니다.
dp[i][j]=sigma{dp[i-1][k](1<=k<=j)}=dp[i][j-1]+dp[i-1][j];
문제풀이 2
1-n에서 매 수는 여러 번 얻을 수 있고 전체 획득 횟수는 2m이며 i를 설정하면 xi,
x1+x2+...xm=2m, 이 방정식의 비음정수해의 개수를 구하고 칸막이법으로 ans=C(n-1+2m, 2m)를 얻을 수 있다.
코드 1

#include
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;
}

코드 2
 

#include
using namespace std;
int main()
{
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,m,c[2000][22];
  cin>>n>>m;
  rep(i,0,n-1+2*m) c[i][0]=1;
  rep(i,1,n-1+2*m)
    rep(j,1,min(i,2*m))
      c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
  cout<1+2*m][2*m];
  return 0;
}