提出 #39046485

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'//交互题删掉
#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sp_el(i,n) " \n"[i==n]//空格换行
using namespace std;
#define ull unsigned ll
#define Tmpl template<typename _T>
const int Size=/*array size*/114514;
const ll MOD=/*modulo number*/998244353;
/*--------gcd & lcm & power--------*/
Tmpl
_T gcd(_T a,_T b)
{
	if(a<b)swap(a,b);
	return b?gcd(b,a%b):a;
}
Tmpl
_T lcm(_T a,_T b){return a*b/gcd(a,b);}
Tmpl
_T pw(_T ds,ll zs)
{
	if(!zs)return 1;
	_T t=pw(ds,zs>>1);t*=t;
	if(zs&1)return t*ds;
	return t;
}
/*--------Integer with modulo--------*/
struct ModInt
{
	ll val;
	ModInt(ll v=0){val=v%MOD;}
	operator ll(){return val;}
	ModInt operator=(const ll v){return (*this)=ModInt(v);}
	ModInt operator+(const ModInt B)const{return (val+B.val)%MOD;}
	ModInt operator+=(const ModInt B){return (*this)=(*this)+B;}
	ModInt operator-(const ModInt B)const{return (val-B.val+MOD)%MOD;}
	ModInt operator-=(const ModInt B){return (*this)=(*this)-B;}
	ModInt operator*(const ModInt B)const{return val*B.val%MOD;}
	ModInt operator*=(const ModInt B){return (*this)=(*this)*B;}
};
ModInt inv(ModInt x){return pw(x,MOD-2);}
ModInt operator/(const ModInt A,const ModInt B)
{return (A*inv(B)).val%MOD;}
ModInt operator/=(ModInt A,const ModInt B){return A=A/B;}
istream& operator>>(istream &in,ModInt &A)
{
	in>>A.val;A.val%=MOD;
	return in;
}
ostream& operator<<(ostream &out,const ModInt A)
{
	out<<A.val;
	return out;
}
const int N=1000005;
ModInt jc[N],ans[N],cat[N];
ModInt C(int n,int m)
{
	return jc[n]/jc[m]/jc[n-m];
}
ModInt f(ModInt n)
{
	return cat[n]*ModInt(n*n+ModInt(2))/ModInt(n+ModInt(2));
}
void Init()
{
	jc[0]=1;
	for(int i=1;i<N;i++)jc[i]=jc[i-1]*ModInt(i);
	cat[0]=1;
	for(int i=1;i<N;i++)cat[i]=cat[i-1]*ModInt(4*i-2)/ModInt(i+1);
	ans[2]=1;
	for(int i=3;i<N;i++)ans[i]=ModInt(4)*ans[i-1]+ModInt(2)*f(i-3);
}
int n;
ModInt lst;
void Solve()
{
	cin>>n;
	cout<<ans[n]<<endl;
}
void QingKong()
{

}
int main()
{
	FIO;
	int T=1;
	cin>>T;
	Init();
	while(T--)
	//while(cin>>n&&n)
	//while(cin>>n)
	{
		Solve();
		QingKong();//多测不清空，抱灵两行泪
	}
	return 0;
}

提出情報

ジャッジ結果