题解 I. gcd -“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛(正式赛)()

传送门

VP 的时候失误推错太多次了,写个博客总结一下

【大意】

求所有长度为 \(m\) 且和为 \(n\) 的正整数序列 \(a\) 的贡献和。其中,每个数列的贡献为 \(\displaystyle \sum_{i>1} \gcd(a_{i-1}, a_i)\cdot w(a_i)\)

【分析】

考虑从 \(m\) 个位置中,选择两个相邻的位置分别填写 \(i, j\) ,则方案数为 \((m-1)\)

剩余的 \(m-2\) 个正整数的和为 \(n-i-j\) ,则等价于模型“\(n-i-j\) 个小球放入 \(m-2\) 个盒子里,要求盒子非空”。由隔板法,方案数为 \(\dbinom {n-i-j-1} {m-3}\)

因此,选中的两个位置分别填写 \(i, j\) 后,对答案的贡献为 \(\displaystyle (m-1)\cdot \dbinom {n-i-j-1} {m-3} \cdot \gcd(i, j)\cdot w(j)\)

我们只需要枚举正整数 \(i, j\) 即可:

\(\displaystyle res=\sum_{i, j\geq 1}(m-1)\cdot \dbinom {n-i-j-1} {m-3} \cdot \gcd(i, j)\cdot w(j)\)

注意到公式中重复出线的 \(i+j\) 项,我们可以直接枚举 \(k=i+j\) :

\(\displaystyle res=(m-1)\sum_{k=2}^n \dbinom {n-k-1} {m-3} \cdot \sum_{i+j=k}\gcd(i, j)\cdot w(j)\)

考虑 \(\gcd(i, j)=\gcd(k-j, j)=\gcd(k, j)\) ,因此有:

\(\displaystyle \sum_{i+j=k}\gcd(i, j)\cdot w(j)=\sum_{j=1}^{k-1} \gcd(k, j)\cdot w(j)=\sum_{j=1}^k \gcd(k, j)\cdot w(j)-k\cdot w(k)\)

因此,现在仅需要求解 \(\displaystyle \sum_{j=1}^k\gcd(k, j)\cdot w(j)\) 即可求得答案

而 \(\displaystyle w(j)=\sum_t c_tj^t\) 有 \(\displaystyle \sum_{j=1}^k\gcd(k, j)\cdot w(j)=\sum_t c_t\sum_{j=1}^k\gcd(k, j)\cdot j^t\)

于是问题简化为如何求解 \(\sum_{j=1}^k\gcd(k, j)\cdot j^t\)

————————

传送门

VP 的时候失误推错太多次了,写个博客总结一下

【大意】

求所有长度为 \(m\) 且和为 \(n\) 的正整数序列 \(a\) 的贡献和。其中,每个数列的贡献为 \(\displaystyle \sum_{i>1} \gcd(a_{i-1}, a_i)\cdot w(a_i)\)

【分析】

考虑从 \(m\) 个位置中,选择两个相邻的位置分别填写 \(i, j\) ,则方案数为 \((m-1)\)

剩余的 \(m-2\) 个正整数的和为 \(n-i-j\) ,则等价于模型“\(n-i-j\) 个小球放入 \(m-2\) 个盒子里,要求盒子非空”。由隔板法,方案数为 \(\dbinom {n-i-j-1} {m-3}\)

因此,选中的两个位置分别填写 \(i, j\) 后,对答案的贡献为 \(\displaystyle (m-1)\cdot \dbinom {n-i-j-1} {m-3} \cdot \gcd(i, j)\cdot w(j)\)

我们只需要枚举正整数 \(i, j\) 即可:

\(\displaystyle res=\sum_{i, j\geq 1}(m-1)\cdot \dbinom {n-i-j-1} {m-3} \cdot \gcd(i, j)\cdot w(j)\)

注意到公式中重复出线的 \(i+j\) 项,我们可以直接枚举 \(k=i+j\) :

\(\displaystyle res=(m-1)\sum_{k=2}^n \dbinom {n-k-1} {m-3} \cdot \sum_{i+j=k}\gcd(i, j)\cdot w(j)\)

考虑 \(\gcd(i, j)=\gcd(k-j, j)=\gcd(k, j)\) ,因此有:

\(\displaystyle \sum_{i+j=k}\gcd(i, j)\cdot w(j)=\sum_{j=1}^{k-1} \gcd(k, j)\cdot w(j)=\sum_{j=1}^k \gcd(k, j)\cdot w(j)-k\cdot w(k)\)

因此,现在仅需要求解 \(\displaystyle \sum_{j=1}^k\gcd(k, j)\cdot w(j)\) 即可求得答案

而 \(\displaystyle w(j)=\sum_t c_tj^t\) 有 \(\displaystyle \sum_{j=1}^k\gcd(k, j)\cdot w(j)=\sum_t c_t\sum_{j=1}^k\gcd(k, j)\cdot j^t\)

于是问题简化为如何求解 \(\sum_{j=1}^k\gcd(k, j)\cdot j^t\)