P6828 Chirp Z-Transform with an Arbitrary Modulus

Everyone should know that the original time and memory limits were 1.23s and 345MB.

Given an $n$-term polynomial $P(x)$ and $c, m$, compute $P(c^0), P(c^1), \dots, P(c^{m-1})$. All answers are taken modulo $10^9+7$.

The first line contains three positive integers $n, c, m$. The second line contains $n$ non-negative integers $a_0, a_1, \dots, a_{n-1}$, representing the coefficients of $P(x)$ from low degree to high degree.

Output one line with $m$ positive integers. The $i$-th number represents $P(c^{i-1})$.

For $100\%$ of the testdata, $1 \le n, m \le 6\cdot10^5$, $0 \le c, a_i < 10^9+7$. | Test Point ID | Limits on $n, m$ | | :-----------: | :-----------: | | $1$ | $n=m=1000$ | | $2$ | $n=m=64000$ | | $3$ | $n=m=5\cdot10^5$ | | $4$ | $n=5\cdot10^5,m=6\cdot10^5$ | | $5$ | $n=6\cdot10^5,m=5\cdot10^5$ | The problem setter regrets that, due to precision and the limitations of Luogu’s built-in materials, it cannot be extended to $10^6$. Hint: $7$ FFT runs might not pass. Hint: The problem setter did not use `long double`. Translated by ChatGPT 5