朝田诗乃 的博客

朝田诗乃 的博客

题解 P5248 【[LnOI2019SP]快速多项式变换(FPT)】

posted on 2019-03-11 20:02:25 | under 题解 |

对于100%的数据,将m带入此多项式,

$$f(m)=a_0+a_1m+a_2m^2+a_3m^3+ \cdots +a_nm^n$$

不难发现,设 $a_na_{n-1}\cdots a_2a_1a_0$ 是一个 $m$ 进制数,将此数转换为10进制即为 $f(m)$ 的值。因此只需要倒序输出 $f(m)$ 在 $m$ 进制下每一位的值即可。

总复杂度 $O(logn)$

当然你也可以模拟过

#include <iostream>
#include <cstdio>
using namespace std;
long long n, m, fm, a[100050];
int main() {
    cin >> m >> fm;
    for(; fm; fm /= m) a[++n] = fm % m;
    printf("%d\n", n);
    for(int i = 1; i < n; ++i) cout << a[i] << " ";
    cout << a[n];
}