같은 것 포함인 오름차순(내림차순이 아닌) 경우의 수

https://codeforces.com/contest/1288/problem/C

Problem - C - Codeforces

Edu 80. div2. C

콘테중에는 못풀었지만 그래도 콘테 끝나고 나서 풀 수 있었음.

나중에 알고보니 아이디어가 참 좋은 문제.

 

a1, a2, ..., am

b1, b2, ..., bm

이렇게 m개의 수열 a, b가 있을 때,

ai <= bi가 되는 경우의 수는? (a, b 수열은 [1,n]의 수로 구성)

답: 2m+(n-1) C 2m

 

일단 b수열을 거꾸로 하게 되면,

a1, a2, ..., am, bm, bm-1, ..., b2, b1이 같은것을 포함 

그럼 2m 길이에 [1,n]숫자를 차례로 부여하면 된다.

만약 숫자를 반드시 하나라도 꼭 써야 한다면 답은 2m C n이 될 것이다.

하지만, 모든 수를 반드시 써야하지 않으니까

숫자1이 쓰이는 개수를 x1, 2는 x2, ..., n은 xn이라고 하면,

x1 + x2 + ... + xn = 2m이 되고 x1을 |형태로 나타내면

|| + ||||| + + ... + ||| = 2m 형태로 볼 수 있다.

즉, '+'는 n-1개 '|' 2m개 존재하므로,

어렸을 때 배웠던 aaaaabbb의 Permutation을 생각해보면 (전체)! / ((a개수)! (b개수)!) 이므로,

(2m + (n-1))! / ((2m)! * (n-1)!) 이다. (즉, 2m+n-1 C 2m인 셈)

나머지는 조합 이용해서 구하면 된다.

 

순열/조합 부분이 잘 이해가 되지 않으면 아래 사이트를 보면 됨.

https://sites.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-gcomb

불러오는 중입니다...

 

근데.. 나는 좀 다르게 풀었음.

위에서 언급했던 Key Idea가 생각나지 않아서

우선은 m길이를 같은것 포함하는 오름차순 경우의 수를 셌더니

m=1일때 m=2일때.. 이렇게 조사해보니 (n+m-1)C(m)이라는 것을 알아냄. (여기까지 한참 걸림)

그 다음 am 숫자가 1이면 a 수열은 m-1길이에 대해서 (1+(m-1)-1)C(m-1)만큼 존재할 것이고,

b수열은 m길이에 대해서 아까와 같은 경우의 수 (n+m-1Cm)만큼이 존재할 것임.

그래서 a수열의 am 숫자(i)가 1부터 n까지 반복문 돌면서 (i+(m-1)-1)C(m-1) * ((n-i+1)+m-1)C(m) 값을 모두 더해서 답을 구함.

 

 

 

#include <cstdio>
using namespace std;
typedef long long ll;
ll d[1111][11];
ll mod = 1e9+7;
ll f(int n, int r) {
    if(r==0 || n==r) return d[n][r]=1LL;
    ll &ret = d[n][r];
    if(ret > 0LL) return ret;
 
    return ret = (f(n-1,r) + f(n-1,r-1)) % mod;
}
int main() {
    int n,m; scanf("%d%d",&n,&m);
    ll ans = 0LL;
    for(int i=1; i<=n; i++) {
        ans += f(i+(m-1)-1,m-1) * f((n-i+1)+m-1,m);
        ans %= mod;
    }
    printf("%lld", ans);
    return 0;
}