P
r
o
b
l
e
m
\mathrm{Problem}
Problem
S
o
l
u
t
i
o
n
\mathrm{Solution}
Solution
设
f
i
f_i
fi 表示
i
i
i 个硬币的期望步数，则有：
f
i
=
p
(
f
i
−
1
+
1
)
+
(
1
−
p
)
(
f
i
−
1
+
f
i
+
1
)
f_i={p(f_{i-1}+1)+(1-p)(f_{i-1}+f_i+1)}
fi=p(fi−1+1)+(1−p)(fi−1+fi+1)
则有：
f
i
=
∏
i
=
1
k
1
/
p
k
f_i=\prod_{i=1}^{k} 1/p^k
fi=i=1∏k1/pk
C
o
d
e
\mathrm{Code}
Code
#include
<bits
/stdc
++.h
>
#define int long long
using namespace std
;
const int P
= 998244353;
int
power(int a
, int b
) {
int res
= 1;
while (b
> 0) {
if (b
& 1) res
= res
* a
% P
;
a
= a
* a
% P
, b
>>= 1;
}
return res
;
}
signed
main(void
)
{
freopen("coin.in","r",stdin
);
freopen("coin.out","w",stdout
);
int p
, k
; cin
>> p
>> k
;
if (p
== 0) return cout
<< k
, 0;
p
= power(p
, P
-2);
int A
= p
;
int B
= 1 - power(p
, k
);
B
= (B
% P
+ P
) % P
;
int C
= 1 - p
;
C
= (C
% P
+ P
) % P
;
A
= A
* B
% P
* power(C
, P
-2) % P
;
cout
<< A
<< endl
;
return 0;
}
