问题 E: 飞碟解除器

时间限制: 1 Sec  内存限制: 128 MB
提交: 21  解决: 15
[提交] [状态] [命题人:admin]

题目描述

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 (注意逆元)

 

代码：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
const ll mod = 998244353;

ll qpow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1){
            ans = ans * a % mod;
        }
        b>>= 1;
        a = a * a % mod;
    }
    return ans%mod;
}

ll inv(ll a){
    return qpow(a , mod - 2);
}
ll k ,p , q, v;

int main(){
    cin >> k >> p >> q >> v;
    ll Q = (1 - p * inv(q)%mod)%mod * inv(k) % mod;
    ll A1 = p * inv(q) % mod * v % mod;
    ll ans = A1 * inv(1 - Q) % mod * inv(1 - Q) % mod;
    cout<<ans<<endl;
    return 0;
}