飞碟解除器-布布扣-bubuko.com

题目描述

wjyyy在玩跑跑卡丁车的时候，获得了一个飞碟解除器，这样他就可以免受飞碟的减速干扰了。
飞碟解除器每秒末都会攻击一次飞碟，但每次只有p/q的概率成功攻击飞碟。当飞碟被成功攻击时，减速状态解除。
如果攻击失败，飞碟会使wjyyy的平均速度变为前一秒的1/k倍。
wjyyy一开始以v m/s的速度行驶，问在减速状态解除时，他期望的行驶距离对998244353取模的结果。

输入

输入共一行，共4个非负整数k,p,q,v。其中gcd(p,q)=1。

输出

输出共一行，表示wjyyy的期望行走距离对998244353取模的结果。

样例输入

2 2 3 9

样例输出

119789331

提示

对于100%的数据，gcd(p,q)=1,1≤k≤998244352,1≤p≤q≤998244352,0≤v≤998244352
提示wjyyy在第一秒走过的距离是v m，如果他此时没有攻击成功，则在第二秒后走过的距离是2×v/k m。
以此类推。

思路：

需要注意的是攻击失败后的减速是整体的平均速度，（整个过程包括之前路程的总的）降到 v/k

所以期望为： v(p/q)+2v(p/q)(1-p/q)/k+3v(p/q)((1-p/q)/k)^2+……

即求n趋向于无穷的差比数列的前n项和，利用错位相减算出 Sn = a1*(1 - Q^n) / (1-Q)^2

因为n趋向于无穷 Q < 1 所以 Sn = a1 / (1-Q) ^ 2

其中 a1 = p / q * v , Q = (1 - p / q) / k (注意逆元)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=998244353;
 5 
 6 ll pow1(ll a,ll b) {
 7     ll res = 1;
 8     while (b) {
 9         if (b & 1) {
10             res = res * a % mod;
11         }
12         b >>= 1;
13         a = a * a % mod;
14     }
15     return res;
16 }
17 
18 ll inv(ll x){
19     return pow1(x,mod-2);
20 }
21 
22 ll k,p,q,v;
23 int main() {
24     scanf("%lld%lld%lld%lld", &k, &p, &q, &v);
25     ll a = p * inv(q) % mod * v % mod;
26     ll Q = ((1 - p * inv(q)+mod) % mod) % mod * inv(k) % mod;
27     ll ans = a * inv(1-Q) % mod * inv(1-Q) % mod;
28     printf("%lld\n", ans);
29 }

View Code

飞碟解除器

原文：https://www.cnblogs.com/Accpted/p/11203971.html