Nowcoder9986F.組合數問題（二項式定理、快速幂）

F.組合數問題

題解：

我覺得相當炸裂的一道題，為什麼大家都會...[裂開][裂開]

((1+1)^n=C(0,n)+C(1,n)+...+C(n,n)=2^n)

((1-1)^n=C(0,n)-C(1,n)+C(2,n)-C(3,n)+...+C(n,n)=0)

兩式相加除2：

(2^{n-1}=C(0,n)+C(2,n)+...+C(n,n))

把其中一個1換成(i)，二項式展開：(二項式定理：((x+y)^{n}=sum_{i=0}^nC(i,n)x^iy^{n-i}))

((1+i)^n=C(0,n)+iC(1,n)-C(2,n)-...+C(n,n))

((1-i)^n=C(0,n)-iC(1,n)-C(2,n)-...+C(n,n))

兩式相加除2：

(((1+i)^n+(1-i)^n)/2=C(0,n)-C(2,n)+C(4,n)-...+C(n,n))

虛數有一個性質：

((1+i)^2=1+2i+i^2=2i)

((1+i)^4=2i*2i=4i^2=-4)

是以

((1+i)^{4n}=(-4)^n)

即(-4^{n/4}=C(0,n)-C(2,n)+C(4,n)-...+C(n,n))

((2^{n-1}+1/2(-4^{n/4}))即為所求。

// Problem: 組合數問題
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9986/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
typedef long long ll;
ll qpow (ll a,ll b) {
	ll ans=1;
	while (b) {
		if (b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main () {
	int n;
	cin>>n;
	cout<<(((qpow(2,n-2)%mod+qpow(-4,n/4)*qpow(2,mod-2)%mod)%mod+mod)%mod);
}