EOJ Monthly 2019.9 (based on September Selection) - D. 站军姿

- ECNU 华东师大月赛D题 -

D. 站军姿

题目描述

“向右看齐”
“向前看”
“ 20 分钟军姿”
每天的军训， Cuber QQ 最喜欢的就是站军姿的环节。因为在站军姿的时候， Cuber QQ 可以看着美丽的丽娃河思考人生。
今天， Cuber QQ 开始观察丽娃河上的鸭子了。 Cuber QQ 近似地把丽娃河看成一个圆形的池塘，他数了数，一共有 n 只鸭子在丽娃河上，鸭子在丽娃河上任意的划水。
Cuber QQ 突发奇想，如果它们的位置是等概率随机的，它们有多大的概率会分布在圆形池塘的同一个半圆内呢？
“眼睛都别闭上了，我看看谁的眼睛闭着让他站到前面来”
教官突然的一句话，打断了 Cuber QQ 的思考，他忘记怎么做了。

输入格式

第一行一个整数 T （ 1≤T≤10⁵ ），代表数据组数。
接下来 T 行，每行一个整数 n （ 1≤n≤10¹⁸ ），代表鸭子的数量。

输出格式

共 T 行，每行一个整数，表示答案。
可以证明答案是一个分数。我们令答案的最简分数是 P/Q，对每一个询问输出 P⋅Q⁻¹mod1 000 000 007，其中 Q⁻¹ 是 Q 在模 1 000 000 007 意义下的逆元。

样例

Input
2
1
2

Output
1
1

提示

鸭子数量为 1 或 2 时，属于同一个半圆的概率是 1。
由于鸭子相比池塘太小了，我们可以把鸭子当作点。

题解

自己想的时候以为概率是（1/2^1-n） ￣□￣｜｜

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
#define inf 1ll<<60
#define zero 1e-7
//n 只鸭子分布在同一个半圆中的概率就是 n*2^(1−n)。
//求逆元 inva≡a^(p−2)(mod p)→ 费马小定理
typedef long long ll;
const int N=1e5+5;
const int maxn=5e3+5;
const ll mod=1e9+7;ll power(ll a, ll k) {ll b=1;while(k) {if(k&1) b=b*a%mod;a=a*a%mod;k>>=1;}return b%mod;
}int main() {int t;ll n;scanf("%d", &t);while(t--) {scanf("%lld", &n);ll res;if(n<=2) res=1;else {//注意看题：最简分数，所以P和Q（即n和temp）要约分ll temp=power(2, n-1);ll g=__gcd(n%mod, temp);n=n%mod/g;temp/=g;res=n*power(temp, mod-2)%mod;}printf("%lld\n", res);}return 0;
}