隐藏
「bsoj5041」挑战nbc - 数论 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj5041」挑战nbc - 数论

题目大意

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


题目分析

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

我们将其化简得:

根据错位相减(错位相减,一减就错)+等比数列求和可得到通项公式:

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}
姥爷们赏瓶冰阔落吧~