题目大意

\(a_0 = 1\)，\(a_n = a_i + a_j\) (\(n \ge 1, i,j\) 均在 \([0,n-1]\) 内均匀随机)

试求出对于给定的 \(n\)，\(a_n\) 的期望值是多少?

解题思路

已知 \(f_0=1,f_1=1\)。

设 \(Q(x)\) 为 \(x\) 的期望值，则有 \(Q(a_n)=\frac{\sum_{i=0}^{n-1} a_i}{n}=\frac{n*(n+1)}{2n}=\frac{n+1}{2}\)。

则有 \(f(n)=Q(a_i+a_j) \ i,j \in [0,n) \\ =Q(a_i)+Q(a_j) \ i,j \in [0,n) \\ = 2Q(a_i) \ i \in [0,n)=n+1\)

AC CODE

#include <bits/stdc++.h>
using namespace std;

#define int long long

int T, n;

signed main()
{
	scanf("%lld", &T);
	while(T--)
	{
		scanf("%lld", &n);
		printf("%lld\n", n + 1);
	}
}