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

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

вход

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

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

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

Jth из следующего 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 года шеф-повар Challenge @ code