传送门：https://ac.nowcoder.com/acm/contest/11161/B
题意
思路
假设栈顶为i，那么下一个入栈的必须是i或者i+1，所以和栈内的状态无关。
设当前为i，下一个放入i+1而不是更大的数字的概率为p，则
$$p=f_i*p+f_{i+1}$$
则：
$$p=\frac{w_{i+1}}{\sum_{k=i+1}^nw_k}$$
则:
$$ans=\prod_{i=2}^np_i$$
复杂度O(n)dp。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll quick_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
void solve() {
int n; cin >> n;
vector<ll> w(n + 100), sum(n + 100);
for(int i = 1;i <= n; i++) cin >> w[i];
for(int i = n;i >= 1; i--) sum[i] = sum[i + 1] + w[i];
ll ans = 1;
for(int i = 2;i <= n; i++) {
ans = ans * w[i] % mod * quick_pow(sum[i] % mod, mod - 2) % mod;
}
cout << ans << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/21/nowcoder-challenge48-b/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！