伯努利数

LibreOJ #138 类欧几里得算法

题意

T1000T \leq 1000 组数据。给定 n,a,b,c[0,109],k1,k2[0,10],k1+k210n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10,求取 x=0nxk1ax+bck2 \sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}

部分分——观察性质

k1=0,k2=1k_1=0,k_2=1 时,是为一般类欧几里得算法的模板。上述链接亦给出了 k1=0,k2=2;k1=1,k2=1k_1=0,k_2=2; k_1=1,k_2=1 时的解法。

k2=0k_2=0 时,该式退化为 x=0nxk1\sum_{x=0}^{n}x^{k_1},即 k1k_1 次的等幂求和。有一个模糊的结论:

nn 为正整数。则kk 次的等幂求和,x=0nxk\sum_{x=0}^{n}x^k,是一个关于 nnk+1k+1 次多项式。

该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊,是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 k+2k+2 个点以插值。

再观察 OI-Wiki 上对于 k1+k22k_1+k_2\leq 2 时的解法。在求取 h(n,a,b,c)=x=0nax+bc2h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2时采取了如下转化:

x2=2×x(x+1)2x=2(y=1xy)xx=0nax+bc2=x=0n2(y=1ax+bcy)ax+bc\begin{aligned} x^2&=2\times \frac{x(x+1)}{2}-x\\ &=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned} \quad\begin{aligned} \Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\ \end{aligned}

这样一来,由于 yy 是一个线性算子,在 ax+bycax+b\geq yc 时都有 yy 向总和贡献,于是我们可以应用类似于 k1=0,k2=1k_1=0,k_2=1 时的方法转化贡献。这个过程对 k2k_2 作了降次。

那么,对于更高次项,有无办法采取同样的办法转化呢?是否可以设计一些转化,使得要求取的函数 f(,k1,k2)f(\cdots,k_1,k_2) 能够由 f(,k1?,k2?)f(\cdots,k_1-?,k_2-?) 推出呢? (更多…)

More
  • 2022年10月13日