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

诗乃

2019-03-11 20:02:25

Solution

对于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)$ 当然你也可以模拟过 ```cpp #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]; } ```