LibreOJ #138 类欧几里得算法
题意
T≤1000 组数据。给定 n,a,b,c∈[0,109],k1,k2∈[0,10],k1+k2≤10,求取
x=0∑nxk1⌊cax+b⌋k2
部分分——观察性质
当 k1=0,k2=1 时,是为一般类欧几里得算法的模板。上述链接亦给出了 k1=0,k2=2;k1=1,k2=1 时的解法。
当 k2=0 时,该式退化为 ∑x=0nxk1,即 k1 次的等幂求和。有一个模糊的结论:
设 n 为正整数。则k 次的等幂求和,∑x=0nxk,是一个关于 n 的 k+1 次多项式。
该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊,是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 k+2 个点以插值。
再观察 OI-Wiki 上对于 k1+k2≤2 时的解法。在求取
h(n,a,b,c)=x=0∑n⌊cax+b⌋2时采取了如下转化:
x2=2×2x(x+1)−x=2(y=1∑xy)−x⟹x=0∑n⌊cax+b⌋2=x=0∑n2y=1∑⌊cax+b⌋y−⌊cax+b⌋
这样一来,由于 y 是一个线性算子,在 ax+b≥yc 时都有 y 向总和贡献,于是我们可以应用类似于 k1=0,k2=1 时的方法转化贡献。这个过程对 k2 作了降次。
那么,对于更高次项,有无办法采取同样的办法转化呢?是否可以设计一些转化,使得要求取的函数 f(⋯,k1,k2) 能够由 f(⋯,k1−?,k2−?) 推出呢? (更多…)