如何用FFT算法O(NlogN)计算模M下多项式在q幂点的取值？

Alright, let's break down how to solve this Polish Olympiad in Informatics problem efficiently. The goal is to compute the values of an N-degree polynomial ( F(x) ) at the points ( q^1 \mod M, q^2 \mod M, ..., q^N \mod M ) in ( O(N \log N) ) time using a variant of FFT tailored for modular arithmetic—Number Theoretic Transform (NTT).

This is a completed task from the Polish Olympiad in Informatics. We're given:

• An N-degree polynomial ( F(x) ) with coefficients ( a_1, a_2, ..., a_N )
• A modulus ( M ), a base ( q ), where ( N ) is a power of two (( N \leq 2^{20} )) and ( q^N \equiv 1 \mod M )
• We need to output ( F(q^1 \mod M), F(q^2 \mod M), ..., F(q^N \mod M) )

Since ( q^N \equiv 1 \mod M ), ( q ) acts as an N-th root of unity modulo ( M ). Evaluating ( F(x) ) at ( q^1, q^2, ..., q^N ) is exactly what NTT is designed to do—compute polynomial evaluations at roots of unity in modular arithmetic, all in ( O(N \log N) ) time.

1. Polynomial Setup
   Define your polynomial as ( F(x) = a_1 + a_2x + a_3x^2 + ... + a_Nx^{N-1} ). Each evaluation we need is ( F(q^k) = \sum_{i=1}^N a_i \cdot (q^k){i-1} = \sum_{i=0}^{N-1} a_{i+1} \cdot q^{k \cdot i} ). This is a direct match for the output of an NTT on the coefficient sequence ( [a_1, a_2, ..., a_N] ).

2. NTT Execution

   • Use an iterative NTT implementation (better for large ( N ) like ( 2^{20} ) to avoid recursion stack issues).
   • Ensure all operations are performed modulo ( M ) to keep numbers manageable and correct. Remember that NTT relies on ( M ) being a prime where ( M-1 ) is divisible by ( N ) (which is guaranteed here since ( q^N \equiv 1 \mod M ) implies such a root of unity exists).

3. Extract Results

   • The standard NTT outputs ( F(q^0), F(q^1), ..., F(q^{N-1}) ).
   • We need ( F(q^1) ) to ( F(q^N) ). Since ( q^N \equiv 1 \mod M ), ( F(q^N) = F(1) ), which is the same as ( F(q^0) ). So our desired outputs are the NTT results from index 1 to ( N-1 ), plus the index 0 result (for ( q^N )).

Let's take the sample mentioned: ( q=5 ), ( N=3 ) (note: normally ( N ) is a power of two, but this is just for illustration). Let ( M=31 ) since ( 5^3 = 125 \equiv 1 \mod 31 ). If ( F(x) = a_1 + a_2x + a_3x^2 ):

• ( F(5^1 \mod 31) = F(5) = a_1 + 5a_2 + 25a_3 )
• ( F(5^2 \mod 31) = F(25) = a_1 + 25a_2 + 5a_3 ) (since ( 25^2 = 625 \equiv 5 \mod 31 ))
• ( F(5^3 \mod 31) = F(1) = a_1 + a_2 + a_3 )

These are exactly the values you'd get from computing the NTT of ( [a_1, a_2, a_3] ) modulo 31.

• Overflow Prevention: Use 64-bit integer types (like long long in C++ or int64 in Python) for intermediate calculations to avoid overflow before taking modulo ( M ).
• Edge Case Handling: When ( N=1 ), ( q^1 \equiv 1 \mod M ), so you just output ( a_1 ) (since ( F(1) = a_1 )).
• NTT Correctness: Double-check that your NTT implementation uses the correct root of unity (here, ( q ) itself) and handles the bit-reversal permutation properly for iterative implementations.

内容的提问来源于stack exchange，提问作者Junak