20.11.13模拟 挑战nbc（nbc）

给定1~n，每次可以合并两个数字，得到平均值，求怎么合并能使得最后剩下的数字最大

显然每次选择最小的两个数字合并是最优策略。我们可以对每个数字用一个加权值 ,显然越大的数字这个权值要用越大的加权值，最大的合并一次，用0.5，次大的合并两次用0.25.
这样我们就可以O（n）解决了。其实1~n这些固定数字显然可以化简式子

\[ \begin{array}{l} S_{n}&=\frac{1}{2^{n}}+\frac{2}{2^{n-1}}+\cdots+\frac{n}{2}(1) \\ 由等比数列求和公式 S_{n}&=\frac{a_1 (1-q^n)}{1-q} =1 \\ 2 S_{n}&=\frac{1}{2^{n-1}}+\frac{2}{2^{n-2}}+\cdots+n(2) \\ \text { (2) }-(1) S_{n}&=n-\frac{1}{2^{n}}-\frac{1}{2^{n-1}}-\cdots-\frac{1}{2}=n-1+\frac{1}{2^{n}} \\ a n s=S_{n}+\frac{1}{2^{n}}&=n-1+\frac{1}{2^{n-1}} \end{array} 去年我写了个矩阵不知道干什么的。。如果看得懂可否告诉我。 \]

#include
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
inline char gt()
{
//	return getchar();
	static char buf[1<<21],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
template 
inline void  read(T &x)
{
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template 
inline void out(T x)
{
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('\n');
}
const int N = 1e9;
vectorv;
int n;

const int mod = 1e9 + 7;
inline lxl qpow(lxl a, int b)
{
	lxl r(1);
	for(; b; a = a * a % mod, b >>= 1) if(b & 1) r = r * a % mod;
	return r;
}

struct matrix
{
	lxl a[5][5];
	int n, m;
	matrix()
	{
		memset(a, 0, sizeof a);
	}
} I, A;
matrix operator *(const matrix &x, const matrix & y )
{
	matrix a;
	a.n = x.n;
	a.m = y.m;
	rep(i, 1, x.n)
	rep(j, 1, y.m)
	rep(k, 1, x.m)
	a.a[i][j] = (a.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
	return a;
}

namespace one{
	int main(){
		cout<<(n-1+qpow(qpow(2,n-1),mod-2) ) %mod;
		return 0;
	}
}

int main()
{
	freopen("nbc.in", "r", stdin);
	freopen("nbc.out", "w", stdout);
	read(n);
	
	one::main();
	return 0;
	
	lxl k = n - 1;
	A.n = 1;
	A.m = 3;
	A.a[1][1] = 1;
	A.a[1][2] = 2;
	A.a[1][3] = 1;

	I.n = I.m = 3;
	I.a[1][1] = I.a[2][1] = qpow(2, mod - 2);
	I.a[2][2] = I.a[3][2] = I.a[3][3] = 1;
	while(k)
		{
			if(k & 1) A = A * I;
			I = I * I;
			k >>= 1;
		}
	out(A.a[1][1] % mod);
	return 0;
}