Submission #26204672

---

Source Code Expand

//AFO countdown:25 Days
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int TT=read();while(TT--) 
#define NO puts("NO");
#define YES puts("YES");
using namespace std;

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

const int Mod=998244353;
const int M=1e7+10;
int n,fac[M],ifac[M],inv[M],pow2[M];

void init(int n){
	inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
	for (int i=2;i<=n;i++)
		inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod,
		fac[i]=fac[i-1]*i%Mod,
		ifac[i]=ifac[i-1]*inv[i]%Mod;
}

int C(int m,int n){return fac[m]*ifac[n]%Mod*ifac[m-n]%Mod;}

signed main(){
	n=read();init(n);
	int res1=1,res2=0;pow2[0]=1;
	for (int i=1;i<=n;i++)
		pow2[i]=pow2[i-1]*2%Mod,res1=res1*3%Mod;
	for (int i=n/2+1;i<=n;i++)
		res2=(res2+C(n,i)*pow2[n-i])%Mod;
	res2=res2*2%Mod,res1=(res1-res2+Mod)%Mod;
	cout<<res1<<endl;
	return 0;
}

Submission Info

Judge Result