zcmimi's blog

arrow_back伯努利数共5篇文章

avatar
zcmimi
2020-08-27 16:32:00

问题

\displaystyle \sum\limits_{i=1}^n i^k

1258 序列求和 V4

普通求法:

$$ (n+1)^{k+1}-

avatar
zcmimi
2020-06-22 21:09:00

https://www.51nod.com/Challenge/Problem.html#problemId=1822

定义

$$ \begin{cases} B0=1\~\ \displaystyle \sum\limits{i=0}^n {n+1\choose i}B_i=0,

avatar
zc
2020-08-23 10:18:00
查看原题

点击跳转

avatar
zc
2020-08-23 10:18:00
查看原题

点击跳转

细节: 如果从n开始有连续一段空白,那么这段空白要去掉

转换后可以发现只需要m+1张牌就可以

考虑每次"亵渎"的贡献

第一次"亵渎"的贡献就是\displaystyle \sum_{i=1}^n i^k剪掉空位的贡献

在空位p上使用"亵渎",有贡献的位置: [p+1,n],贡献为\displaystyle \sum_{i=1}^{n-p} i^k

减去空位多算的贡献即可

求自然数幂和可以考虑拉格朗日插值,递推法,伯努利数等

avatar
zc
2020-08-08 20:19:00
查看原题

点击跳转

\begin{aligned} &\quad\sum_{i=1}^n \gcd(i,n)^x lcm(i,n)^y \\ &=\sum_{i=1}^n \frac{in}{lcm(i,n)}^x lcm(i,n)^y \\ &=\sum_{i=1}^n (in)^x lcm(i,n)^{y-x} \\ &=\sum_{i=1}^n (in)^x \frac{in}{\gcd(i,n)}^{y-x}\\ &=\sum_{i=1}^n (in)^y \gcd(i,n)^{x-y} \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^n i^y [\gcd(i,n)=d] \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^{n/d} (id)^y [\gcd(i,n)=1] \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^{n/d} (id)^y \sum_{k|i,k|n}\mu(k) \\ &=n^y\sum_{d|n} d^{x-y}\sum_{k|\frac nd}\mu(k)\sum_{i=1}^{n/dk} (idk)^y \\ &=n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y\sum_{i=1}^{n/dk} i^y \end{aligned}

\displaystyle S_k(n)=\sum_{i=1}^{n-1}i^k,可以看做一个y+1次多项式,假设求出后每一项系数为t_i

=n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^yS_y(\frac n{dk}) \\ =n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y\sum_{i=0}^{y+1}t_i(\frac n{dk})^i \\ =n^y\sum_{i=0}^{y+1}t_i \sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y (\frac n{dk})^i

其中,设\displaystyle Z(n)=\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y (\frac n{dk})^i ,

可以看成f(d)=d^x,g(d)=\mu(d)d^y,h^i(d)=d^i这三个积性函数的狄利克雷卷积

卷积后还是积性函数,且狄利克雷卷积满足交换律,只有当x=1x=p^k\mu(x)\ne 0

\begin{cases} Z(1)=1\\ Z(p)=p^x-p^y+p^i\\ Z(p^k)=(f * h^i)(p^k)-(f * h^i)(p^{k-1}) \cdot p^y \end{cases}

其中\displaystyle (f * h^i)(p^k)=\sum_{i+j=k} f(p^i)\cdot h^i(p^j)

使用Pollard-Rhon分解质因数,枚举每个质因子(包括次幂),然后狄利克雷卷积计算答案

1/1
Search
search