输入两个整数A和B，输出它们的和
input 3 4 output 7Test
以下是表格样例与本题无关
| **数据点编号** | $p\le$ | **特殊性质** |
|---|---|---|
| 1 | $100$ | |
| 2 | $10^6$ | $\ $ |
| 3 | A | |
| 4 | $10^9$ | A |
| 5 | $10^9$ | B |
| 6 | $10^9$ | |
| 7 | A | |
| 8 | B | |
| 9 | ||
| 10 |
abc
| 数据1 | 数据2 |
|---|---|
| $\le 10$ | $\le 10^{10}$ |
https://www.cnblogs.com/zhiyangfan/p/16014605.html
题目 $$\left(\sum_{i=0}^n\sum_{j=0}^i\left(\binom{i}{j}\times i\times j\right)\right)\bmod P$$ 思路 纯属直接推式子了。 前置知识 组合数 $C_{i}^j$ 根据组合数的定义，它有这样一个性质： $\sum_{i=0}^n C_{n}^i = 2^n$
式子 先不看 $\bmod$ ，看中间的式子。 $\sum_{i=0}^n \sum_{j=0}^i C_i^j \times i \times j$ 把组合数拆开 $= \sum_{i=0}^n \sum_{j=0}^i \dfrac{\frac{i!}{(i-j)!}}{j!} \times i \times j$ $=\sum_{i=0}^n \sum_{j=0}^i \dfrac{i \times (i-1)!}{j \times (j-1)! \times (i-j)!} \times i \times j$ $= \sum_{i=0}^n \sum_{j=0}^i \dfrac{i^2 \times (i-1)!}{(j-1)!\times (i-j)!}$ $=\sum_{i=0}^n i^2 \times\sum_{j=0}^i \dfrac{(i-1)!}{(j-1)! \times ((i-1)-(j-1))!}$ $=\sum_{i=0}^n i^2 \times 2^{i-1}$ （这里运用到了组合数的性质） $= \sum_{i=1}^n i^2 \times 2^{i-1}$ 令 $S = \sum_{i=1}^n i^2 \times 2^{i-1}$，则： $2S - S = \sum_{i=1}^n i^2\times 2^i - \sum_{i=1}^n i^2 \times 2^{i-1}$ 错位相减，用 $i^2 \times 2^i - (i+1)^2 \times 2^i$，则： $S = (\sum_{i=1}^{n-1} i^2 \times 2^i - (i+1)^2 \times 2^i) + n^2 \times 2^n - 1^2 \times 2^0$ $= (\sum_{i=1}^{n-1} 2^i \times (i^2 - (i+1)^2)) + n^2 \times 2^n - 1$ $=(\sum_{i=1}^{n-1} 2^i \times (-2i-1)) + n^2 \times 2^n - 1$ $=(-\sum_{i=1}^{n-1} 2^i \times 2i + 2^i) + n^2 \times 2^n - 1$ $=-(\sum_{i=1}^{n-1} 2^i + 2\times \sum_{i=1}^{n-1} 2^i \times i) + n^2 \times 2^n -1$ $=-(2^n - 2 + 2 \times \sum_{i=1}^{n-1} 2^i \times i) + n^2 \times 2^n - 1$ 令 $T = \sum_{i=1}^{n-1} 2^i \times i$，则： $2T - T = \sum_{i=1}^{n-1} 2^{i+1} \times i - \sum_{i=1}^{n-1} 2^i \times i$ 错位相减，得： $T=(\sum_{i=1}^{n-2} 2^{i+1} \times i - 2^{i+1} \times (i+1)) + 2^n \times (n-1) - 2^1 \times 1$ $=(-\sum_{i=1}^{n-2} 2^{i+1}) + 2^n \times (n-1) - 2$ $=-(2^n - 4) + 2^n \times (n-1) - 2$ 带入 $S$，得： $S = -(2^n - 2 + 2 \times (-(2^n-4) + 2^n \times (n-1) - 2)) + n^2 \times 2^n - 1$ $=-(-2^{n+2} + 2^{n+1} \times n + 2^n +2) + n^2 \times 2^n - 1$ $=2^{n+2} - 2^{n+1} \times n - 2^n + n^2 \times 2^n -3$ $=2^{n}\times (4 - 2 \times n - 1 + n^2) - 3$ $=2^{n} \times (n^2 - 2 \times n + 3) - 3$ 最后，用个快速幂即可 $O(\log n)$ 算出。