VOJ 跳一跳题解动态规划

2024-04-22 01:04

文章标签 动态规划题解 voj

本文主要是介绍VOJ 跳一跳题解动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

跳一跳

题目描述

现有一排方块，依次编号为 $1\ldots n$ 。
方块 1 上有一个小人，已知当小人在方块 i 上时，下一秒它会等概率地到方块 i（即不动），方块 i+1，方块 i+2……方块 n 上。
求小人到达方块 n 所需要的期望时间（单位：秒）。

输入格式

一个数字 n。

输出格式

若答案 $ans=\frac{A}{B}$ 输出 $\times B^{-1} \bmod (10^9+7)$ 。其中 $B^{-1}$ 表示 $\bmod (10^9+7)$ 下的逆元。

样例 1

输入样例

输出样例

样例 2

输入样例

10000000

输出样例

406018741

数据范围与约定

对于 $50\%$ 的数据， $\leqslant 10^6$ 。
对于 $100\%$ 的数据， $\leqslant n \leqslant 10^7$ 。

思路

设 $d p [i]$ 为从 i 点出发到达 n 点的期望时间，然后从后向前递推。

原题

LOJ6342——传送门

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 6;
const ll mod = 1e9 + 7;
int inv[maxn]; // 逆元
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;inv[0] = 1;inv[1] = 1;for (int i = 2; i <= n; i++) // 预处理逆元inv[i] = mod - mod / i * inv[mod % i] % mod;ll dp = 0;  // 为了避免MLE，不能开dp数组ll sum = 0; // sum记录后缀和for (int i = n - 1; i >= 1; i--){dp = (sum + n - i + 1) * inv[n - i] % mod;sum += dp;sum %= mod;}cout << dp << '\n';return 0;
}