数学题可爱捏~
Hint
Analysis
注意到形式很好看,猜测是某种神奇迭代。
考虑特殊情况 \(k=1\),于是有:
\(g(i)=\sum_{i_1\mid i}f(i_1)=(f*1)(i)\)$
即 \(g=f*1\)。
于是猜测 \(g=f*1^k\),这里的幂运算表示多次 Dirichlet 卷积。
简单证明一下,采用数学归纳法:
基本情况 \(k=1\),已经证过,不在赘述。
当有
\[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1})=f*1^{k-1} \]时,左式卷 \(1\) 得:
\[\begin{align*} \text{LHS}*1&=[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1})]*1 \\\ &=\sum_{d\mid i}[\sum_{i_1\mid d}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1})]\cdot 1(\frac{i}{d}) \\\\ &=\sum_{d\mid i}\sum_{i_1\mid d}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1}) \\\\ &=\sum_{i_1\mid i}\sum_{i_2\mid i_1}\sum_{i_3\mid i_2}\cdots\sum_{i_k\mid i_{k-1}} f(i_{k}) \end{align*}\]右式卷 \(1\) 得:
\(\quad\text{ }\text{ }\text{RHS}*1=f*1^{k-1}*1=f*1^k\)
于是有:
\[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\sum_{i_3\mid i_2}\cdots\sum_{i_k\mid i_{k-1}} f(i_{k})=f*1^k \]于是由 \(k-1\) 的情况可以得到 \(k\) 的情况,归纳性的,易得,
\(\color{red}{\text{Lemma:}}\)
对任意 \(k \in \mathbb{Z^*}\),有:
即 \(g=f*1^k\)。
于是使用快速幂计算 \(1^k\) 的卷积,单次卷积 \(O(n\log n)\),总时间复杂度 \(O(n\log n\log k)\)。
Code
// 咕咕咕~
标签:log,卷积,题解,Clarke,mid,cdots,HDU5628,text,sum
From: https://www.cnblogs.com/godmoo/p/18531033