普通にDPをしても \(O(N)\) で間に合う． 今回は遷移が線形なので，行列冪乗で遷移を計算すれば \(O(log N)\)．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename T>
M<T> operator * (M<T> a, M<T> b){
M<T> c;
int n = a.size();
c.resize(n);
rep(i,n) c[i].resize(n);
rep(i,n) rep(j,n){
rep(k,n){
c[i][j] += a[i][k]*b[k][j];
}
}
return c;
}
int main() {
ll n,pi;
cin >> n >> pi;
M<mint> mat, a, unit;
a.resize(3);
rep(i,3) a[i].resize(3);
unit.resize(3);
rep(i,3) unit[i].resize(3);
rep(i,3) unit[i][i] = mint(1);
mat = unit;
mint q = mint(100-pi) / mint(100);
mint p = mint(pi) / mint(100);
a[0][0] = q;
a[1][0] = p;
a[2][0] = mint(1);
a[0][1] = mint(1);
a[2][2] = mint(1);
M<mint> pow = a;
while(n){
if(n & 1){
mat = mat * pow;
}
n >>= 1;
pow = pow*pow;
}
cout << (mat[0][1] + mat[2][1]).val() << endl;
return 0;
}
