[더블릿 - 18] 3 의 배수/moft

프로그램 명: moft

제한시간: 1 초

운명의 마술사 Fate는 숫자놀이를 하다 "우연히" 문제를 만들게 되었다.

"k개의 자릿수에 1..n개의 수를 넣어서 3의 배수가 되는 경우의 수를 구해보자. 각 수는 중복되어도 상관없다."

예를 들어 n = 3 , k = 4 라고 하자. 그랬을 경우 다음과 같이 나올것이다.

1 1 1 3
1 1 2 2
1 1 3 1
1 2 1 2
1 2 2 1
...
3 3 3 3
1 1 1 3

우리의 목적은 다음과 같은 경우의 수를 모두 세는 것이다. 숫자가 너무 커질 수 있으므로 54,321로 나눈 나머지를 출력해주자.

입력

두 수 n, k가 주어진다. ( 1 ≤ n ≤ 100,000, 1 ≤ k ≤ 100,000 )

출력

경우의 수를 54,321로 나눈 나머지를 출력한다.

입출력 예

입력

3 4

출력

27

출처:Fate

여러 방면으로 생각하다 보니 푸는데 오래 걸렸다.

처음으로는 일반화된 식을 찾을 수 있을까? 를 생각해보았는데

못찾았다.

그 다음으로 생각해본게 점화식으로 나타낼 수 있을까? 였다.

또, 그 점화식이라는게

어느 항들로 이루어지는지를 찾아야했다.

다음은 내가 생각한 방법이다.

p.s.

int형을 쓰니 int범위를 벗어나 wrong answer가 나왔다.

daum equation editor 사용

moft 수식 원본.txt

#include <iostream>

using namespace std;

 

int n, k;

long long c[3], v[3], p[3], m = 54321;

 

int Func()

{

    for (int i = 1; i < k; ++i)

    {

        p[0] = v[0] % m;

        p[1] = v[1] % m;

        p[2] = v[2] % m;

        v[0] = c[0]*p[0] + c[2]*p[1] + c[1]*p[2];

        v[1] = c[2]*p[2] + c[1]*p[0] + c[0]*p[1];

        v[2] = c[1]*p[1] + c[2]*p[0] + c[0]*p[2];

    }

    return v[0] % m;

}

 

int main()

{

    cin >> n >> k;

 

    v[0] = p[0] = c[0] = n / 3;

    v[1] = p[1] = c[1] = (n + 2) / 3;

    v[2] = p[2] = c[2] = (n + 1) / 3;  

 

    cout << Func();

    return 0;

}