【JZOJ A组】苹果

Description

1.1 Background
快是上元时候了。
只见楼边一个女子捂着肚子，长发披肩，全身白衣，头发上束了一条金带，白雪一映，更是灿然生光……
“咕∼∼∼”
咳，像小S一样的女神，自然是不会被鸽的。
那么只有一种解释了……
1.2 Piece
你永远填不满小S的胃，就像你永远也叫醒不了一个装睡的人。
1.3 Description
正如你所想的那样，小S又饿了。
所以她也只能暂且抛弃心中的烧鹅仔，西湖醋鱼，葱包桧，蒸熊掌，白切鸡，白肚儿……将目光放的短浅一些了……大概要自力更生了……QwQ……
咳咳……
楼的对面有一颗苹果树，生了三年又三年，终于是有了一树的果实……
能被小S看中的苹果树自然不是普通的苹果树。
它是一颗线段树，更特殊的是，它的根结点1的长度是2^k，深度则是0
受制于懒惰，小S会使用手中Extremely Strong的工具等概率随机的选取一个区间进行采摘，对于一个区间[L, R]，我们定义它的价值：
f(L, R) = 在线段树上询问时包含L和包含R的两个区间的深度之和特殊的，如果有区间同时包含了L和R，那么这个区间的深度算两次。
程式化的，我们这么描述这颗树和询问函数：
{
void Build(int o, int l, int r) {
if(o > 1) dep[o] = dep[o >> 1] + 1;
if(l == r) return;
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
}
void Query(int o, int l, int r, int x, int y) {
if(x <= l && r <= y) {
all.push_back((Interval){l, r});
return;
}
int mid = l + r >> 1;
if(x <= mid) Query(o << 1, l, mid, x, y);
if(mid < y) Query(o << 1 | 1, mid + 1, r, x, y);
}
}
即
f(L, R) = depall.front() + depall.back()
现在，她想知道她能获的苹果数量的期望，即E[f]

Input

共一行，一个正整数n，表示根结点所代表的区间是[1, 2^n]

Output

共一行，一个整数ans，满足ans ≡ E[f] (mod 10^9 + 7)

Sample Input

2

Sample Output

3

见选手下发文件中A_ex0.in/ans，A_ex1.in/ans。

Data Constraint

思路

题解说AK这场模拟赛脸线段树都不用学。。。难得一匹

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const long long p=1000000007;
long long n,ans;
long long qui(long long x,long long k)
{
	x%=p;
	long long base=x,sum=1;
	while(k)
	{
		if(k&1) (sum*=base)%=p;
		(base*=base)%=p;
		k>>=1ll;
	}
	return sum;
}
int main()
{
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	scanf("%lld",&n);
	if(n==0)
	{
		printf("0");
		return 0;
	}
	(ans=((n-1)%p*qui(2,n+1)+2)%p*(1+qui(2,n-1)))%=p;
	(ans*=qui(((1+qui(2,n))*qui(2,n-1))%p,p-2))%=p;
	printf("%lld\n",ans);
	return 0;
}