Найдите значение полинома для некоторых K различных целых чисел по модулю 786433.

Вам дан полином степени N с целыми коэффициентами. Ваша задача — найти значение этого многочлена для некоторых K различных целых чисел по модулю 786433.

Ввод

Первая строка входных данных содержит целое число N, обозначающее степень многочлена.

Следующая строка каждого набора входных данных содержит (N+1) целые числа, обозначающие коэффициенты многочлена. i-е число в этой строке обозначает коэффициент a_(i-1) в многочлене a_0 + a_1 × x_1 + a_2 × x_2 + .. . + a_N × x_N.

Следующая строка содержит одно целое число Q, обозначающее количество запросов.

j-я из следующих строк Q содержит целое число x_j, обозначающее запрос.

Вывод

Для каждого запроса выведите одну строку, содержащую ответ на соответствующий запрос. Другими словами, j-я строка вывода должна содержать целое число, равное a_0 + a_1 × x_j + a_2 × x_j^2 + ... + a_N × x_j^N по модулю 786433.

Ограничения и подзадачи

• 0 ≤ a_i, x_j < 786433
• Подзадача №1 (37 баллов): 0 ≤ N, Q ≤ 1000
• Подзадача №2 (63 балла): 0 ≤ N, Q ≤ 2,5 × 10^5

Пример

Ввод: 2 1 2 3 3 7 8 9

Выход: 162 209 262

Пояснение

Пример 1.

• Запрос 1: 1 + 2 × 7 + 3 × 7 × 7 = 162
• Запрос 2: 1 + 2 × 8 + 3 × 8 × 8 = 209
• Запрос 3: 1 + 2 × 9 + 3 × 9 × 9 = 262

Вот код, который выполняется за время O(n log n). Я использую быстрое преобразование Фурье, чтобы умножить два полинома.

Почему мне нужно использовать оператор по модулю 786433 для всех вычислений? Я понимаю, что это может быть связано с переполнением int? Это нормально в вопросах соревновательного программирования?

#include <cstdio>
#include <algorithm>
#include <vector>
#include <sstream>
#include <iostream>

using namespace std;

#define all(a) (a).begin(),(a).end()
#define pb push_back
#define sz(a) ((int)(a).size())
#define mp make_pair
#define fi first
#define se second

typedef pair<int, int> pint;
typedef long long ll;
typedef vector<int> vi;

#define MOD 786433
#define MAGIC (3*(1<<18))

const int root = 10;

void fft(vi &a, int wn = root)
{
    int n = sz(a);
    if (n == 3)
    {
    int a1 = a[0] + a[1] + a[2];
        int a2 = (a[0] + a[1] * 1LL * root + a[2] * (root * 1LL * root)) % MOD;
        a[1] = a1;
        a[2] = a2;
        return;
    }

    vi a0(n / 2), a1(n / 2);
    for (int i = 0, j = 0; i<n; i += 2, ++j)
    {
        a0[j] = a[i];
        a1[j] = a[i + 1];
    }
    int wnp = (wn * 1LL * wn) % MOD;
    fft(a0, wnp);
    fft(a1, wnp);

    int w = 1;
    for (int i = 0; i<n / 2; ++i) {
        int twiddle = (w * 1LL * a1[i]) % MOD;
        a[i] = (a0[i] + twiddle) % MOD;
        a[i + n / 2] = (a0[i] - twiddle + MOD) % MOD;
        w = (w * 1LL * wn) % MOD;
    }
}    

int n;
vi coef;

void poly(stringstream& ss)
{
    ss >> n;
    n++;
    for (int i = 0; i<n; i++)
    {
        int x;
        ss >> x;
        coef.pb(x);
    }
    while (sz(coef)<MAGIC)
        coef.pb(0);

    vi ntt = coef;
    fft(ntt);

    vector<pint> sm;
    sm.pb(mp(0, coef[0]));
    int pr = 1;
    for (int i = 0; i<sz(ntt); i++)
    {
        sm.pb(mp(pr, ntt[i]));
        pr = (pr * 1LL * root) % MOD;
    }
    sort(all(sm));

    int q;
    ss >> q;
    while (q--)
    {
        int x;
        ss >> x;
        int lo = 0, hi = sz(sm) - 1;
        while (lo<hi)
        {
            int m = (lo + hi) / 2;
            if (sm[m].fi<x)
            lo = m + 1;
            else
            hi = m;
        }
        printf("%d\n", sm[lo].se);
    }
}


void test1()
{
    stringstream ss;
    {
        int degree = 2;
        ss << degree << "\n";
        string coefficients{ "1 2 3" };
        ss << coefficients << "\n";
        int NoQueries = 3;
        ss << NoQueries << "\n";
        int query = 7;
        ss << query << "\n";
        query = 8;
        ss << query << "\n";
        query = 9;
        ss << query << "\n";
    }
    poly(ss);
}

int main()
{
    test1();
    return 0;
}

Кстати. Этот вопрос взят из июльского конкурса 2016 г.