Link with EQ

Title Link

Main idea of the title: Yes n n n seats. At first, the first person will randomly choose a position to sit down, and later people will choose a position farthest from the nearest person to sit down, no matter what position they choose( + 1 +1 +1 or − 1 -1 − 1) if all the people are seated, it's over.

The difficulty of this problem is that everyone will choose a location farthest from the nearest person. There may be multiple locations. Although the probability is equal, if we don't know the specific state, we can't figure out how many such locations, but it's obviously impossible for us to consider the specific state. So we think about whether there is a fixed state, that is, first calculate the state that someone will sit in a certain position next time, and finally see whether this state can be used to calculate all States. Magically, it can.

set up f i f_i fi = total i i i stools, and people have been seated at both ends of the stool, and other positions are empty. This is the expectation of people who can sit in the initial state ( i > 1 ) (i>1) (i>1)
So first we have f 3 = f 4 = 2 f_3=f_4=2 f3 = f4 = 2, for other cases, we set j = ( i + 1 ) / 2 j=(i+1)/2 j=(i+1)/2. Obviously, in this case, a person can only sit in the middle, then:
f i = f j + f i + 1 − j − 1 f_i=f_j+f_{i+1-j}-1 fi​=fj​+fi+1−j​−1
Note: This is actually for i i If i is an even number, there are two options, but the two cases are exactly the same and the probability is the same, so you can calculate one directly.

set up g i g_i gi = total i i i stools, and one end of the stool is occupied by people, and other positions are empty. This is the expectation of people who can sit in the initial state
So we first have g 1 = g 2 = 1 g_1=g_2=1 g1 = g2 = 1. In other cases, a person must sit at another endpoint, then we have:
g i = f i g_i=f_i gi​=fi​

set up h n h_n hn = total n n n stools, all positions are empty, which is the expectation of people who can sit in the initial state.
h 1 = 1 h_1=1 h1​=1
h n = ∑ i = 1 n 1 n ( g i + g n + 1 − i − 1 ) = 1 n ∑ i = 1 n ( g i + g n + 1 − i − 1 ) = 2 n ( ∑ i = 1 n g i ) − 1 h_n=\sum\limits_{i=1}^n\frac{1}{n}(g_i+g_{n+1-i}-1)=\frac{1}{n}\sum\limits_{i=1}^n(g_i+g_{n+1-i}-1)=\frac{2}{n}(\sum\limits_{i=1}^ng_i)-1 hn​=i=1∑n​n1​(gi​+gn+1−i​−1)=n1​i=1∑n​(gi​+gn+1−i​−1)=n2​(i=1∑n​gi​)−1

So we just have to deal with it g i g_i The prefix and of gi ， we can get all the answers.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

const ll mod = 1e9 + 7;

int n;

ll inv[N];

ll f[N], sumg[N], h[N];

ll ksm(ll base, ll n) {
	ll ans = 1;
	while(n) {
		if (n & 1ll) ans = ans * base % mod;
		base = base * base % mod;
		n >>= 1ll;
	}
	return ans;
}

void init(int n) {
	inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		inv[i] = ksm(i, mod - 2);
	}
	f[3] = f[4] = 2;
	for (int i = 5; i <= n; ++i) {
		int j = (i + 1) / 2;
		f[i] = (f[j] + f[i + 1 - j] - 1 + mod) % mod;
	}
	sumg[1] = 1; sumg[2] = 2;
	for (int i = 3; i <= n; ++i) {
		sumg[i] = (sumg[i - 1] + f[i]) % mod;
	}
	h[1] = 1;
	for (int i = 2; i <= n; ++i) {
		h[i] = (2ll * inv[i] % mod * sumg[i] % mod - 1 + mod) % mod;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	init(1e6);
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		printf("%lld\n", h[n]);
	}
}