20.06.27 개발일지 - 謎紛芥索紀 (Large)

https://www.acmicpc.net/problem/14731

14731번: 謎紛芥索紀 (Large)

100K개의 다항식의 도함수 f'(x)에 대해 x = 2일 때의 값을 1B + 7로 나눈 나머지를 구하는 문제이다.

매우 간단하지만, 연산 시간을 맞추는 것에 어려움이 많았다.

 

우선 차수가 1B까지 나올 수 있는 지수 연산이 문제였다.

처음에는 greedy하게 하나하나 해봤지만, 역시나 시간이 부족했다.

 

그 다음에는 2배수로 나눠서 연산을 해보려 했으나,

반대로 입력받은 지수 값을 2진수로 계산하는 것이 너무 오래 걸렸습니다.

 

결국 답은 지수를 10진수 단위로 끊는 것이었습니다.

10^n 단위로 미리 연산을 해두고, 이를 이용한 pow 함수를 따로 제작하여 이를 사용하였습니다.

 

하지만 이후에도 수차례 통과하지 못했습니다.

여러 차례 수정을 하다가 깨달은 점은, 지수 부분만 unsigned long long으로 하였으나

sizeof(unsigned int) 크기를 넘어갈 수 있다는 점이었습니다.

 

그래서 size를 제외한 모든 값을 unsigned long long으로 선언을 해주고 나서야 비로소 통과 할 수 있었습니다.

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

array<unsigned long long, 10> decpow;

unsigned long long GetPow(unsigned int dec)
{
    if (dec == 0)
    {
        return 1;
    }
    int rest = 0, index = 0;
    unsigned long long output = 1;

    while (dec > 0)
    {
        rest = dec % 10;
        dec /= 10;
        for (int i = 0; i < rest; ++i)
        {
            output *= decpow[index];
            output %= 1000000007;
        }
        ++index;
    }

    return output;
}

int main()
{
    unsigned int size = 0;
    unsigned long long output = 0, a = 1, b = 0, value = 2, exp = 1;
    vector<pair<unsigned long long, unsigned long long>> input;
    decpow[0] = 2;
    for (int i = 1; i < 9; ++i)
    {
        exp = 1;
        for (int j = 0; j < 10; ++j)
        {
            exp *= value;
            exp %= 1000000007;
        }
        value = exp;
        decpow[i] = value;
    }

    cin >> size;
    for (int i = 0; i < size; ++i)
    {
        cin >> a >> b;
        if (b > 0)
        {
            input.push_back(make_pair(a * b % 1000000007, b - 1));
        }
    }

    sort(input.begin(), input.end(), [](auto& a, auto& b)
        {
            return a.second < b.second;
        });

    for (const auto& iter : input)
    {
        output += iter.first * GetPow(iter.second);
        output %= 1000000007;
    }

    cout << output << endl;
    return 0;
}