Письменный код за линейное время как решение проблемы ДП, но получение нелогичных ответов

Question

Я написал следующий код для решения этой проблемы hackerrank :

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,k,x;
    cin>>n>>k>>x;
    double a,b;
    long int answer[n-1];
    if (x == 1)
        answer[1] = k-1;
    else 
        answer[1] = k-2;
    for (int i=3;i<=n-1;i++)
    {
        a = k-1;
        b = i-1;
        answer[i-1] = pow(a,b)-answer[i-2];
    }

    cout<<answer[n-2]<<endl;


    return 0;
}

Я пытался отлаживать его часами и не нашел несоответствия с моим O (N) решением для времени , Я получаю тот же отрицательный ответ для больших вводов n, k, x: например, 50 50 50

Я спрашиваю не об очках, а в образовательных целях.

Answer 1

Это из-за переполнения. В основном вы пытаетесь сохранить слишком большие числа для обработки int. Вы можете использовать long long для хранения больших чисел, но даже у них есть ограничение. Я вижу, что проблема дает номер, чтобы использовать его в качестве мода. Вы можете использовать этот номер, чтобы убедиться, что ваш ответ не переполнен, смоделировав свои ответы над этим номером.