H-Jackpot（icpc合肥）

本文主要是介绍H-Jackpot（icpc合肥），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

（1）条件：

1. 有n条路，每条路上有一只青蛙；
2. 每条路有k+1个方格，每条路完全相同，初始时都在第一个方格；
3. 每次可往前跳，跳到前面i个格子概率总是相同，但不会往回跳；
4. 跳到头后就不会再动了；

（2）问题：求将n条路青蛙全部跳到终点的期望次数；

（3）分析：

1. 注意到n条路彼此独立且同情况，所以单算一条路期望次数乘n即可；
2. 对于单条路，E[k+1] = (E[k] + 1 + E[k - 1] + 1 + ... + E[1] + 1)/(k + 1)；注意到数据范围1000，直接递归计算即可；
3. 考虑预处理，到时直接调用乘n即可；

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
#define int ll
#define endl '\n'const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;int qpow (int a, int b) {int res = 1;while(b) {if(b & 1) {res = res * a % mod;}b >>= 1;a = a * a % mod;}return res;
}int dp[N];int dfs(int x) {if (x == 1) return 0;if(dp[x]) return dp[x];int sum = 0;for (int i = x - 1; i >= 1; i--) {sum += dfs(i) + 1;sum %= mod;}sum = sum * qpow(x - 1, mod - 2) % mod;return dp[x] = sum;
}signed main() {ios::sync_with_stdio(false);dfs(1001);int T = 1;cin >> T;while (T--) {int n, k;cin >> n >> k;cout << dp[k + 1] * n % mod << endl;}
}

这篇关于H-Jackpot（icpc合肥）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---