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

这题好像没有pascal题解啊，那我来水一发

感觉没看懂出题人的题解啊

显然，这题一个明显的想法是暴力算出x,x^2,...,x^n，然后再计算a0,a1...am，

那就这么做呗，因为f(m)<=10^18，所以不用高精度，直接依次计算即可。

但如果每次都用ans:=x^(n-1)*n这个算法的话，

显然很可能会出现2^18乘2^18的爆int64的情况，

所以要特判一下(具体见代码和注释)，最后用f(m) mod a[m]作为ans[m]，

f(m) mod a[m-1]作为ans[m-1]...依次类推即可。

显然，当m>f(m)时，答案即为f(m)

如果还是没搞懂，那就举个栗子吧

比如m=12 f(m)=169,

题意即为169=ans[0]+ans[1]12^1+ans[2]12^2，求ans[0],ans[1],ans[2];

那么就用a数组储存12的平方次，即a=[0,12,144];

用169先除以144，得ans[3]=169 div(整除) 144=1,相应的要把169-144*1=25；

再用25 div 12=2,即ans[2]=2,25-12*2=1;

最后剩下一个1就是ans[1]了，

var
n,j,k,m,s,t,t1:int64;//f(m),m<=10^18，要开int64/long long
i:longint;
a,b:array[0..1000005] of int64;//a数组表示0，x,x^2...x^n得值,b即为上面的ans数组
begin
readln(n,m);
t:=n;
t1:=m;//用t和t1代替n,m去做处理
s:=1;
if n>m then//特判一下m>f(m)这种特殊情况
begin
writeln(1);
writeln(m);
halt;
end;
while true do
begin
inc(s);
a[s]:=t;
if t1 div t<n then break;//防爆int64做的特判
// t1:=t1-t;
t:=tn;//每次n代表多项式的系数扩大n倍，即题中的x^n
end;
if a[s]=0 then dec(s);//0*任何正数=0，故可以省略(这句其实可以不加吧，反正加不加都对)
writeln(s);
//for i:=1 to s do write(a[i],' ');
for i:=s downto 2 do//从最高位除起，防止出现答案>m的情况
begin
b[i]:=m div a[i];
m:=m mod a[i];
end;
b[1]:=m;//最后剩下一个常数作为ans[0]
for i:=1 to s do write(b[i],' ');
end.

有什么感想？