数学题 4

标签：10 cdot sum Ans 数学题 n2 aligned

遇到一道题，转化后长这样：

Statement

给出 \(n(\le 10^{10})\)，计算：

\[ n+\sum_{i=0}^{n-1}i\cdot 2^{n-i-1} \]

多组数据，答案对 \(10^9+7\) 取模。

Solution

当时看数据范围以为要用某种根号时间来计算，就一直想不出来，交了暴力就走了

之后打表发现 \(Ans(n)=2^n-1\)。。。

知道结论后你当然有一百万种方法去证他，这里写一个：

\[ \begin{aligned} Ans(n) &= n + \sum_{i=0}^{n-1}i\cdot 2^{n - i - 1}\\ &= n + \sum_{i=0}^{n-1}(n-i-1)\cdot 2^i\\ &=n+(n-1)\cdot\sum_{i=0}^{n-1}2^i-\sum_{i=0}^{n-1}i\cdot 2^i \end{aligned} \]

熟悉 7FA4 的朋友们马上就知道这个问题严格弱于 H4.1.6.2（那篇 blog 的 T1）

H4.1.6.2（节选，需仔细看）：

设 \(T_0=\sum_{i=1}^n2^i\)，则 \(T_0=2^{n+1}-2\)

设 \(T_1=\sum_{i=1}^ni2^i\)，则 \(2T_1=\sum_{i=1}^ni2^{i+1}=\sum_{i=1}^{n+1}(i-1)2^i\)

\(T_1=2T_1-T_1=n2^{n+1}-\sum_{i=1}^n2^i=n2^{n+1}-T_0=(n-1)2^{n+1}+2\)

我们把通项式子代入马上就出来了：

\[ \begin{aligned} Ans(n)&=n+(n-1)\cdot(2^n-1)-((n-2)2^n+2)\\ &=n+n\cdot 2^n-2^n-n+1-n\cdot 2^n+2\cdot 2^{n}-2\\ &=2^n-1 \end{aligned} \]

证完了。

标签：10,cdot,sum,Ans,数学题,n2,aligned
From： https://www.cnblogs.com/laijinyi/p/18370359