21034 - Go To Goal

문제 번역

0번 칸부터 $ 2N + M$번 칸까지 $2N + M + 1$개의 칸이 있는 게임 판이 있습니다. 당신은 0번 칸에 있고 특수 카드 $N$장과 일반 카드 $M$장을 가지고 있습니다. 특수 카드를 사용하면 2칸을, 일반 카드를 사용하면 1칸을 갈 수 있습니다. 이때, 특수 카드는 연속해서 3번 사용할 수 없습니다. 마지막 칸에 도착할 수 있는 경우의 수를 구하세요.

step 1

$N$과 $M$이 작으면 dp로 해결할 수 있습니다. 하지만 그러기에는 드가 너무 많죠. 결국 경우의 수를 구하는 문제니 수학으로 접근해 봅시다.

0부터 시작하는 카운트가 하나 있다 생각해 봅시다. 특수 카드를 쓰면 카운트가 1 증가하고 일반 카드를 쓰면 카운트가 0으로 초기화 됩니다. 카운트가 2를 넘지 않도록 모든 카드를 사용하는 경우의 수를 구하면 됩니다.

저희는 $M$번의 초기화 기회가 있습니다. 그럼 $M+1$번 동안 특수 카드를 어떤 식으로 쓰는지가 중요할 것입니다.

아래는 $N=7, M=4$일때의 예시입니다.

 

step 2

이 문제는 다음 문제로 바꿀 수 있습니다.

$M+1$개의 상자가 있고 각 상자에 $N$개의 돌을 넣습니다. 이때, 한 상자에 최대 2개의 돌만 들어갈 수 있습니다. 돌을 넣을 수 있는 경우의 수를 구하세요.

 

돌이 1개 들어간 상자의 수가 정해진다면 돌이 2개, 0개 들어간 상자의 수도 정해집니다. 그럼 순열을 이용해서 경우의 수를 구할 수 있습니다.

돌이 1개 들어간 상자가 0개, 1개,... , $M+1$개일 때에 대해 답을 구하고 전부 더해주면 됩니다. $1!, 2!,..., (M+1)!$을 전처리로 구해주고 페르마 소정리(https://codestudycafe.tistory.com/3)를 이용하면 쉽게 구할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long int fac[500000],MOD=1000000007;
long long int pow(long long int x, long long int y) {
    if (y == 1) return x;
    long long int val = pow(x, y / 2);
    val *= val;
    val %= MOD;
    if (y % 2 == 0) return val;
    return val * x % MOD;
}
long long int com(long long int x, long long int y) {
    return (fac[x] * pow((fac[y] * fac[x - y] % MOD), (MOD - 2))) % MOD;
}
int main() {
    long long int n, m, i, j,cnt=0;
    fac[0] = 1;
    for (i = 1;i <= 400000;i++) {
        fac[i] = fac[i - 1] * i;
        fac[i] %= MOD;
    }
    scanf("%lld%lld", &n, &m);
    for (i = 0;i <= m + 1;i++) {
        if ((n - i) % 2 != 0) continue;
        if (i + (n - i) / 2 > m + 1) continue;
        if ((n - i) / 2 < 0) continue;
        cnt += (com(m + 1, i) * com(m + 1 - i, (n - i) / 2)) % MOD;
        cnt %= MOD;
    }
    printf("%lld", cnt);
    return 0;
}