题解：
我觉得相当炸裂的一道题，为什么大家都会...[裂开][裂开]
\((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);
}
Nowcoder9986F.组合数问题（二项式定理、快速幂）
原文：https://www.cnblogs.com/zhanglichen/p/14521470.html