ABC 042_D. Iroha and a Grid

* 최적화된 답은 아니지만 공부한 것들의 기록을 위한 코드와 관련 지식을 정리하고자 합니다.

* 출제자가 원하는 답까지는 못 가도 일단 풀어내기 위한 노력을 하려 합니다. 한 단계 성장을 위해서 !

* 회사에서 C 쓰다 요즘 CPP을 쓰다보니까 두 언어가 섞여 쓰게 되었습니다. 충분히 고려하면서 cpp을 쓰기엔 문제 풀기에도 바쁜 시간..T^T

 

D. Iroha and a Grid

D - Iroha and a Grid

 

#include <iostream>
using namespace std;

#define MODULO  (1000000007)
#define MOD(x)  (x%MODULO)
#define MAXNUM  (100001 * 2)
uint64_t fac[MAXNUM] = { 0, };
       
void MakeFactorial(void)
{
    fac[0]=1;
    fac[1]=1;
    for(uint32_t i = 2 ; i < MAXNUM; i++)
    {
        fac[i] = MOD(fac[i-1]*i);
    }
    return;
}

void GetExtendGCD(uint32_t a, uint32_t b, int64_t * x)
{
    uint32_t r0 = a;
    uint32_t r1 = b;
    int64_t x0 = 0;
    int64_t x1 = 1;
    int64_t q;
    while(r1 != 1)
    {
        int64_t tmp = r0;
        q = r0/r1;
        r0 = r1;
        r1 = tmp%r1;

        tmp = x0;
        x0 = x1;
        x1 = tmp - x1*q;
    }

    if(x1 < 0)
    {
        x1 += MODULO;
    }
    *x = MOD(x1);
    return;
}
 
int64_t GetInversion(uint32_t a)
{
    int64_t x;
    GetExtendGCD(MODULO, a, &x);

    return MOD(x);
}

uint64_t GetPermutation(uint32_t a, uint32_t b)
{
    uint32_t n = a + b;
    uint64_t UP = fac[n];
    uint64_t DOWN = MOD(GetInversion(MOD(fac[a] * fac[b])));
    
    return MOD(UP*DOWN);
}
int main(void)
{
    uint32_t H, W, A, B;
    cin >> H >> W >> A >> B;

    MakeFactorial();
    uint32_t result = 0;
    int x, y;
    for(uint32_t i = B; i < W; i++)
    {
        uint64_t upper = GetPermutation(H-A-1, i);
        uint64_t lower = GetPermutation(W-i-1, A-1);

        result += MOD(upper * lower);
        result = MOD(result);
    }
    
    cout << result << endl;
    return 0;
}

 

- 정말 오래 걸려서 풀었다. 수학을 손에 놓은지 좀 오래되었고, 정수론에 대해서 공부를 해야한다는 느낌은 계속 얻고 있었다. 이렇게 제대로 마주칠 줄이야..! 문제 풀이 아이디어보다 수학적인 부분을 제대로 짚어가느라 며칠동안 붙들고 있었다.

중학교 때 경로 찾기 연산이란 것을 알아채고 어떻게 하면 좋을지 고민을 많이 했다. 그냥 막연하게 더할지..등등 

문제가 무엇을 찾는 것인지는 알았는데, 경로 찾기가 조합으로 접근할 수 있단 것을 이번에 알았다. 

학교다닐 때 전혀 그런 접근법을 알려준 사람이 없었다.. 아마,, 공부하면서 아는 풀이가 나오면 더 공식적으로 접근하는 방법을 알려고 하지 않았어서 였을지도..(인강도 안보고 공부했었다)

 

우선 길찾기 연산에 대해서 좌상단을 (0, 0) 우하단을 (h, w)라고 하자. 각 칸의 주소로 좌상단에서 우하단으로 가는 방향의 조합의 개수를 찾는 문제이다. 

우측으로 이동하는 개수는 w 개, 아래로 이동하는 개수를 h개라고 하면, 총 w+h 개의 선택지에 대하여, 우측이동 h개 뽑고, 좌측 이동 w개 뽑는 것과 같다.

-> (w+h)!/(w!h!)

 

가지 못하는 칸들에 대해서 연산을 하려면 

(A->B1) * (B1'->C) + (A->B2)*(B2'->C) ... 와 같이 계산해야한다. 

B1->C 가 아닌 B1'->C 인 이유는 B1 을 시작점으로하면 B2 를 거쳐가는 경로가 중복으로 계산되기 때문이다. 

이 값들은 계속 사용되기 때문에 factorial 값은 미리 한번만 계산해서 저장해둔다. (계속 반복문을 돌릴 필요가 없다)

 

이제 문제는 modulo 의 나눗셈이다.

막연하게 modulo 연산하면 된다 생각해서 조합에 factorial 값에 modulo 연산을 하였는데, modulo 연산은 나눗셈에 닫혀있지 않다는 것을 알았다.

이 경우 잉여역원인 (w! * h!)^(-1)을 구하여 (w+h)!*((w!*h!)^(-1))를 구하며 modulo 연산을 해준다. 

 

잉여역원을 구하는 방법은 확장 유클리드 호제법을 이용하여 구할 수 있다. 이에 대한 구현 내용은 코드로 대체한다.

ax + by = gcd(a,b) 임을 이용하는 것으로, 1000000007을 M이라 하면,

a = M , b = (w!(mod M))*(h!(mod M)) 이라고 할 수 있다.

이 때, a는 prime number 로 gcd(a, b) 는 1이다.

또한, Mx(mod M) + by (mod M) = 1 (mod M)

by (mod M) = 1 (mod M) ( Mx 는 M의 배수) 이므로 

b의 잉여역원이 y이다.