cf - 1452D - Radio Towers

// 找规律
分子是斐波拉契数列,分母是2 ^ n.

#include<iostream>

using namespace std;

const int mod = 998244353,N = 200010;
typedef long long ll;
ll a[N];

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

int main()
{
    a[1] = a[2] = 1;
    for(int i = 3; i < N; i ++) a[i] = (a[i - 1] + a[i - 2]) % mod;
    
    int n;
    cin >> n;
    int fm = qmi(2,n);
    cout << a[n] * qmi(fm,mod - 2) % mod << endl;
}