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

· · 题解

对于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];
}