Description：

求： $$ \sum_{k=1}^n(k\times\sum_{j=1}^k\sum_{i=0}^{n-1}(C^{k-j}_i\times C^{j-1}_{n-i-1})) $$ $1\leqslant n\leqslant10^9$

Solution1：

$$ \begin{align} 原式&=\sum_{k=1}^n(k\times\sum_{j=1}^k\sum_{i=0}^{n-1}(C^{k-j}_i\times C^{j-1}_{n-i-1}))\\ &=\sum_{k=1}^n(k\times\sum_{i=0}^{n-1}\sum_{j=1}^k(C^{k-j}_i\times C^{j-1}_{n-i-1}))\\ &=\sum_{k=1}^n(k\times \sum_{i=0}^{n-1}\sum_{j=0}^{k - 1}(C^j_i\times C^{k-1-j}_{n-i-1})) \end{align} $$

发现后面那个的组合意义就是把序列拆成两部分，枚举在 $n-1$ 个中前 $i$ 个中选 $j$ 个，那后 $n-i-1$ 个中选 $k-1-j$ 个，根据组合意义，发现这个就是 $C^{k-1}_{n-1}$ 。 $$ \begin{align} 原式&=\sum_{k=1}^n(k\times\sum_{i=0}^{n-1}C_{n-1}^{k-1})\\ &=\sum_{k=1}^n(k\times n\times C_{n-1}^{k-1})\\ &=n\times\sum_{k=1}^n(k\times\frac{(n-1)!}{(k-1)!(n-k)!})\\ &=\sum_{k=1}^n(k^2\times C_n^k) \end{align} $$ 分析一下这个式子的组合意义会发现代表先选一个大小为 $k$ 的子集，然后在子集中选两个，可以相同，那么先看那两个，如果他们不同，那么有 $n(n-1)$ 种可能，包含它的子集有 $2^{n-2}$ 个，如果相同，有 $n$ 种可能，包含它的子集有 $2^{n-1}$ 个，所以答案为： $$ n(n-1)\times2^{n-2}+n\times2^{n-1} $$

Solution：

观察一下最后一个求和号的组合含义，可以发现相当于枚举第 $k-j+1$ 个的位置 $i+1$ ，在前面 $i$ 个里选 $k-j$ 个，后面 $n-i-1$ 个里选 $j-1$ 个，所以： $$ \begin{align} 原式&=\sum_{k=1}^n(k\times\sum_{j=1}^kC_n^k)\\ &=\sum_{k=1}^n(k^2\times C_n^k)\\ &=n\sum_{k=1}^n(k\times C_{n-1}^{k-1}) \end{align} $$ 根据组合恒等式： $$ kC_n^k=nC_{n-1}^{k-1} $$ 把 $k-1$ 拆开： $$ \begin{align} 原式&=n\sum_{k=1}^n((k-1)C_{n-1}^{k-1}+C_{n-1}^{k-1})\\ &=n\sum_{k=1}^n(n-1)C_{n-2}^{k-2}+n\sum_{k=1}^nC_{n-1}^{k-1}\\ &=n(n-1)2^{n-2}+n2^{n-1} \end{align} $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

#define MOD 1000000007

ll n;

ll power(ll a,ll b)

{

	if(b == 0)return 1;

	if(b < 0)return 0;

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	freopen("goddess.in","r",stdin);

	freopen("goddess.out","w",stdout);

	cin >> n;

	cout << ((n - 1) * n % MOD * power(2ll,n - 2) % MOD + n * power(2ll,n - 1) % MOD) % MOD << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}