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)\)
标签：正整数,gcd,cdot,题解,sum,纬杯,displaystyle,dbinom From： https://www.cnblogs.com/JustinRochester/p/16924690.html