开篇 \(————\sum\)的本质
\(\sum\)其实可以理解为for循环
例如 $$ \sum_{i = 1}^{n} i $$
其实就是代码中
int ans=0;
for(int i=1;i<=n;i++) ans+=a[i];
ans的值
求和的运算定律
分配律
\[\sum_{i \in K} c * i = c * \sum_{i \in K} i \]很简单，不解释
反过来同理
结合律
\[\sum_{i \in K} a_i + \sum_{i \in K} b_i = \sum_{i \in K} (a_i + b_i) \]反过来同理
换元法
\[\sum_{i \in K} a_i = c * \sum_{p(i) \in K} a_{p(i)} \]可以理解为换了一个枚举方法，具体例子见例1
应用（逝一逝）
例1
\[\sum_{k = 1}^{n} k \]求递推式
\[\sum_{k = 1}^{n} k \]换元
\[=\sum_{k = 1}^{n} n-k+1 \]拆开
\[=\sum_{k = 1}^{n} n+1 - \sum_{k = 1}^{n} k \]不难发现前面那个 $\sum $ 其实就是 $ n * （n+1）$，后面那个 $\sum $ 其实就是求和公式
\[\sum_{k = 1}^{n} k = n * (n+1) - \sum_{k = 1}^{n} k \]合并同类项
\[2\sum_{k = 1}^{n} k = n * (n+1) \]系数化简
\[2\sum_{k = 1}^{n} k = \frac{n * (n+1)}{2} \]既可
例2
\[\sum_{k = 1}^{n} 2^k*k \]求递推式
\[设 S_n=\sum_{k = 1}^{n} 2^k*k \]把k换成k-1
\[= \sum_{k = 0}^{n-1} 2^{k+1} * (k+1) \]展开（k+1）
\[= \sum_{k = 0}^{n-1} 2^{k+1} * k + 2^{k+1} \]提出 \(2^{k+1}\)
\[= 2\sum_{k = 0}^{n-1} 2^{k} * k + \sum_{k = 0}^{n-1} 2^{k+1} \]把后面那个$ \sum $ 的 $ k+1 $ 换回k，前面那个 $ \sum $ 可以发现 $ k=0 $ 时不对答案做贡献，所以可以直接把前面的 $ k $ 调成从 \(1\) 开始
\[= 2\sum_{k = 1}^{n-1} 2^{k} * k + \sum_{k = 1}^{n} 2^{k} \]不难发现后面那个 \(\sum\)其实就是等比数列之和，直接用公式
\[= 2\sum_{k = 1}^{n-1} 2^{k} * k +2^n-2 \]不难发现前面那个 \(\sum\)其实就是 \(S_{n-1}\)
\[= 2S_{n-1} +2^n-2 \] 标签：那个,前面,数论,sum,int,寒假,ans,集训,其实 From： https://www.cnblogs.com/yyx525jia/p/17033366.html