MOD = 998244353
N = 3 * 10 ** 5 + 1
fac = [1] * N
rev = [1] * N
f = [1] * N
for i in range(2, N):
f[i] = (f[i - 1] + (i - 1) * f[i - 2]) % MOD
for i in range(2, N):
fac[i] = fac[i - 1] * i % MOD
rev[i] = pow(fac[i], MOD - 2, MOD)
def C(n, k):
return fac[n] * rev[k] % MOD * rev[n - k] % MOD
def solve(n):
res = 0
for i in range(n):
if 4 * i > n:
break
res = (res + C(n - 2 * i, 2 * i) * fac[2 * i] * rev[i] * f[n - 4 * i]) % MOD
print(res % 998244353)
t = int(input())
for _ in range(t):
n = int(input())
solve(n) // ॐ
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
#define pb push_back
#define Sort(a) sort(a.begin(),a.end())
#define ff first
#define ss second
const int N = 3e5 + 10;
const ll f = 998244353;
vll fact(N,1),ifact(N,1),pairs(N,1);
ll binpow(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1)
res = res * a % f;
a = a * a % f;
b >>= 1;
}
return res;
}
ll nCr(int n, int r){
ll t = (ifact[r]*ifact[n-r])%f;
return (t * fact[n])%f;
}
void pre(){
for (int i = 2; i < N; ++i){
fact[i]=(fact[i-1]*i)%f;
}
for (int i = 1; i < N; ++i){
ifact[i]=binpow(fact[i],f-2);
}
for (int i = 2; i < N; ++i){
pairs[i] = (pairs[i-1] + pairs[i-2]*(i-1))%f;
}
}
void solve(){
int n;
cin>>n;
ll ans = 0;
for (int i = 0; i <= n; i+=4){
ll t = nCr(n-i/2,i/2);
ll g = (fact[i/2]*ifact[i/4])%f;
t = (t * g)%f;
t = (t * pairs[n-i])%f;
ans+=t; ans%=f;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pre();
int t=1;
cin>>t;
while(t--)
solve();
}
1472B - Fair Division | 1281C - Cut and Paste |
141A - Amusing Joke | 112A - Petya and Strings |
677A - Vanya and Fence | 1621A - Stable Arrangement of Rooks |
472A - Design Tutorial Learn from Math | 1368A - C+= |
450A - Jzzhu and Children | 546A - Soldier and Bananas |
32B - Borze | 1651B - Prove Him Wrong |
381A - Sereja and Dima | 41A - Translation |
1559A - Mocha and Math | 832A - Sasha and Sticks |
292B - Network Topology | 1339A - Filling Diamonds |
910A - The Way to Home | 617A - Elephant |
48A - Rock-paper-scissors | 294A - Shaass and Oskols |
1213A - Chips Moving | 490A - Team Olympiad |
233A - Perfect Permutation | 1360A - Minimal Square |
467A - George and Accommodation | 893C - Rumor |
227B - Effective Approach | 1534B - Histogram Ugliness |