组合数问题 题解(虚数)

题目链接

题目大意

计算

题目思路

如果是计算

显然

两式相加

而下面就有点神奇要类比，想到虚数第一次真想不到

而

则

则

而

最终

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,mod=998244353;
ll n;
ll qpow(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1){
            ans=ans*base%mod;
        }
        b=b>>1;
        base=base*base%mod;
    }
    return ans;
}
int main(){
    scanf("%lld",&n);
    ll ans=((qpow(2,n)+2*qpow(-4,n/4))*qpow(4,mod-2)%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}