「bsoj5041」挑战nbc - 数论

题目大意

Abwad现在拿到了难度为1,2,3,……,n的n道原题，每次操作他可以挑出任意两道题，并使用一种叫做“NOIP二合一”的方法合成一道难度为其平均值的题。Abwad希望在操作了n-1次之后，最后剩下的那道题难度最大。

---

题目分析

显然我们从小到大合并可以做到最后的难度最大。
我们可以得到以下式子：

$$Ans=\frac{\frac{\frac{1+2}{2}+3}{2}+4}{2}\cdots$$

我们将其化简得：

$$Ans=\frac{1+2\times 2^0+3\times 2^1\cdots n\times 2^{n-2}}{2^{n-1}}$$

根据错位相减（错位相减，一减就错）+等比数列求和可得到通项公式：

$$Ans=\frac{(n-1)2^{n-1}+1}{2^{n-1}}$$

因为模是个质数，求个逆元即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
LL mod=1000000007;
LL Quick_Pow(LL a,LL b) {
	LL ans=1;
	while(b) {
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
LL n;
int main() {
	n=Get_Int();
	LL Up=((n-1)*Quick_Pow(2,n-1)%mod+1)%mod,Down=Quick_Pow(2,n-1);
	printf("%lld\n",Up*Quick_Pow(Down,mod-2)%mod);
	return 0;
}