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; }