题面链接

题面

PROBLEM DESCRIPTION

今晚飞行棋大师 $Legend\_dy$ 不是很想学习于是邀请 $Jeneveuxpas$ 和 $LZVSDY$ 一起来玩把飞行棋，赛前放下豪言势必要血虐他们。没想到成了小丑，四连胜就此终结.

$Jeneveuxpas$ 三辆飞机抵达终点，剩下的一辆飞机也已率先进入直道，本以为自己已经胜券在握了，没想到连摇了十来次骰子都没能摇进终点，让 $LZVSDY$ 后来居上夺走了胜利的果实，他非常难过百思不得其解提出了这样一个问题：

有 $n+1$ 个的格子编号 $0$ 到 $n$，$0$ 号格子为起点，$n$ 号格子为终点.

花费 $1$ 的代价等概率随机 $[1,n]$ 中的一个整数 $x$，向终点走 $x$ 步，若达到终点还有剩余步数则反向行走。如果随机到了数字 $n$ 并且未抵达终点则 赠送 一次等概率随机 $[1,n−1]$中整数 $y$ 的机会，并向终点走 $y$ 步，若达到终点还有剩余步数则反向行走。问期望花费多少代价能恰好抵达终点？

INPUT

第一行输入一个正整数 $T$ ，表示一共有 $T$ 组测试用例，$1 \leq T \leq 100$.

接下来 $T$ 行，每行输入一个整数 $n$，即题目描述的 $n$，$6\leq n\leq 10^9$.

OUTPUT

对每个测试用例，输出一行一个整数，表示期望花费代价对 $10^9+7$ 取模的结果.

SAMPLE INPUT

1
998244353

SAMPLE OUTPUT

3168436

解题思路

• 一开始位于起点$0$，如果掷出$n$，则可以直接到达终点，概率为$\frac{1}{n}$，对期望的贡献为$1 \times \frac{1}{n} = \frac{1}{n}$.
• 第一次投掷出不为$n$的值，概率为$\frac{n - 1}{n}$，如果两次投掷骰子到达终点，有两种可能，第一种投掷出$n - i_{第一次走的步数}$，概率为$\frac{1}{n}$，第二种投掷出$n$ 通过奖励的次数来到达终点，概率为 $\frac{1}{n} \times \frac{1}{n - 1}$，对期望的总贡献为$\frac{n - 1}{n} \times (\frac{1}{n} + \frac{1}{n} \times \frac{1}{n - 1}) \times 2 = \frac{1}{n} \times 2$.
• 如果第二次未到达终点，概率为$1 - (\frac{1}{n} + \frac{1}{n} \times \frac{1}{n - 1}) = \frac{n - 2}{n - 1}$， 第三次到达终点的概率同第二次，所以总的贡献为$\frac{1}{n} \times \frac{n - 2}{n - 1} \times 3$.
• 递推得到第$i$次到达终点对期望的贡献$\frac{i}{n} \times (\frac{n - 2}{n - 1})^{i - 2}$，其中$i \geq 2$.
• 期望 = $\sum_{i = 2}^{\infty}\frac{i}{n} (\frac{n - 2}{n - 1})^{i - 2} + \frac{1}{n}$，设$a = \frac{n - 2}{n - 1}$.

$$ \begin{align} 原式 =& \frac{1}{na} \sum_{i = 2}^{\infty} i a^{i - 1} + \frac{1}{n}\\ =& \frac{1}{na} (\frac{d}{da} \frac{1}{1 - a} - 1) + \frac{1}{n}\\ =& \frac{1}{n} (\frac{1}{(1 - a) ^ 2} - 1) + \frac{1}{n}\\ =& \frac{1}{n} (1 + \frac{2 - a}{(1 - a) ^ 2}) \end{align} $$

AC代码

#include <bits/stdc++.h>
#define int long long
using ll = int;
using PII = std::array<int, 2>;
using namespace std;
const ll INF = 2e18 + 10;
#ifdef __clang__
   template <typename T>
   inline int my_lg(T n) {return (n > 0) ? static_cast<int>(log2(n)) : -1;}
   #define __lg my_lg
   #define __gcd gcd
#endif
// struct cmp{bool operator()(const int & x, const int &y) const{ return x<y;}};
const int N = 2E6 + 10;
template <class T>
constexpr T power(T a, ll b) {
   T res = 1;
   for (; b; b /= 2, a *= a) {
       if (b % 2) {
           res *= a;
       }
   }
   return res;
}

constexpr ll mul(ll a, ll b, ll p) {
   ll res = a * b - ll(1.L * a * b / p) * p;
   res %= p;
   if (res < 0) {
       res += p;
   }
   return res;
}

template <int P>
struct Mint {
   int x;
   constexpr Mint() : x{} {}
   constexpr Mint(ll x) : x{norm(x % getMod())} {}

   static int Mod;
   constexpr static int getMod() {
       if (P > 0) {
           return P;
       } else {
           return Mod;
       }
   }
   constexpr static void setMod(int Mod_) { Mod = Mod_; }
   constexpr int norm(int x) const {
       if (x < 0) {
           x += getMod();
       }
       if (x >= getMod()) {
           x -= getMod();
       }
       return x;
   }
   constexpr int val() const { return x; }
   explicit constexpr operator int() const { return x; }
   constexpr Mint operator-() const {
       Mint res;
       res.x = norm(getMod() - x);
       return res;
   }
   constexpr Mint inv() const {
       assert(x != 0);
       return power(*this, getMod() - 2);
   }
   constexpr Mint &operator*=(Mint rhs) & {
       x = 1LL * x * rhs.x % getMod();
       return *this;
   }
   constexpr Mint &operator+=(Mint rhs) & {
       x = norm(x + rhs.x);
       return *this;
   }
   constexpr Mint &operator-=(Mint rhs) & {
       x = norm(x - rhs.x);
       return *this;
   }
   constexpr Mint &operator/=(Mint rhs) & { return *this *= rhs.inv(); }
   friend constexpr Mint operator*(Mint lhs, Mint rhs) {
       Mint res = lhs;
       res *= rhs;
       return res;
   }
   friend constexpr Mint operator+(Mint lhs, Mint rhs) {
       Mint res = lhs;
       res += rhs;
       return res;
   }
   friend constexpr Mint operator-(Mint lhs, Mint rhs) {
       Mint res = lhs;
       res -= rhs;
       return res;
   }
   friend constexpr Mint operator/(Mint lhs, Mint rhs) {
       Mint res = lhs;
       res /= rhs;
       return res;
   }
   friend constexpr std::istream &operator>>(std::istream &is, Mint &a) {
       ll v;
       is >> v;
       a = Mint(v);
       return is;
   }
   friend constexpr std::ostream &operator<<(std::ostream &os, const Mint &a) {
       return os << a.val();
   }
   friend constexpr bool operator==(Mint lhs, Mint rhs) {
       return lhs.val() == rhs.val();
   }
   friend constexpr bool operator!=(Mint lhs, Mint rhs) {
       return lhs.val() != rhs.val();
   }
};

template <>
int Mint<0>::Mod = 1e9+7;
// int Mint<0>::Mod = 998244353;

template <int V, int P>
constexpr Mint<P> CInv = Mint<P>(V).inv();

constexpr int P = 1e9+7;
// constexpr int P = 998244353;
using Z = Mint<P>;

void SINGLE_TEST() 
{
   ll n; cin >> n;
   Z a = ((Z)n - (Z)2) / ((Z)n - 1);
   Z b = ((Z)1 + ((Z)2 - a) / (((Z)1 - a) * ((Z)1 - a))) / (Z)n;
   cout << b << "\n";
}

signed main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr),cout.tie(nullptr);

   int SAMPLES = 1;
   cin >> SAMPLES;
   for(int CUR=1;CUR<=SAMPLES;CUR++){
       SINGLE_TEST();
   }
}