c++ - 求 K 个不同整数处多项式的值，模 786433

Question

给你一个具有整数系数的 N 次多项式。您的任务是找到此多项式在一些 K 个不同整数处的值，模 786433。

输入

输入的第一行包含一个整数 N，表示多项式的次数。

每个测试用例的下一行包含 (N+1) 个整数，表示多项式的系数。此行中的第 i 个数字表示多项式 a_0 + a_1 × x_1 + a_2 × x_2 + .. 中的系数 a_(i-1) . + a_N × x_N.

下一行包含一个整数Q，表示查询的数量。

以下 Q 行中的第 j 行包含一个整数 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 33个78个9

输出:162209262

解释

示例案例 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;
}

顺便说一句:这question来自2016年7月的挑战@code chef

Answer 1

回复

” Why do I need to use the modulo 786433 operator for all calculations? I understand that this might relate to int overflow? It this normal in competitive programming questions?

是的，这是为了避免溢出。

是的，这在编程问题集和竞赛中很正常。