有名公式

• 等差数列の和 = (初項 + 末項)×項数 / 2
  • 出題例: ABC360 E - Random Swaps of Balls
• $\displaystyle \sum_{k=1}^n k = \frac{1}{2} n(n+1)$
• $\displaystyle \sum_{k=1}^n k^2 = \frac{1}{6} n(n+1)(2n+1)$
• $\displaystyle \sum_{k=1}^n k^3 = \left[ \frac{1}{2} n(n+1) \right]^2$
• $\displaystyle \sum_{k=1}^n \sum_{l=1}^k l = \sum_{k=1}^n \frac{1}{2}k(k+1) = \frac{1}{6} n(n+1)(n+2)$
• $\displaystyle \sum_{k=1}^{n} r^{k-1} = \frac{1-r^n}{1-r}$ ($r \neq 1$ のとき)
  • 合成数 mod の場合は 2×2 の行列の行列累乗で求められる。
    • 参考: 漸化式

有名パターン

• 連続整数の積の和
• 等差×等比型
  • $\displaystyle \sum_{k=1}^n kr^{k-1} = \frac{nr^{n+1}-(n+1)r^n + 1}{(1-r)^2}$ ($r \neq 1$のとき)
  • 証明
  • 派生として、2次式×等比もある。同じようにやると等差×等比の形に帰着する
  • 行列累乗でも解ける（3×3の行列を作ることになる）
    • 合成数 mod の場合など、逆元が存在するとは限らない場合は行列累乗をすることになる。
    • 参考: 漸化式

総和と総積の組合せ

• $\displaystyle \sum_{S\subseteq [n]} \prod_{i\in S} a_i = \prod_{i\in[n]} (1 + a_i)$