F - 组合数问题

首先呢我们知道

由

①

和

②

把一式和二式相加并除二我们就得到

③

因为
所以三式子的结果是

我们又知道

④

所以三式四式相加除二即得出答案

#include<iostream>
#define ll long long
using namespace std;

const int MOD = 998244353;
ll Q_power(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % MOD;
        b >>= 1;
        a = a* a % MOD;
    }
    return res ;
}

ll X_1(ll x){return Q_power(x , MOD - 2) ; }

int main(){
    ll n ; cin >> n;
    ll ans = Q_power(4,n/4) % MOD;
    if((n / 4) & 1) ans = - ans + MOD;
    ll tmp = Q_power(2 , n - 1);
    ans = (ans + tmp) % MOD * X_1(2) % MOD;
    cout << ans << endl;
    return 0;
}