题解
简单分析一下，有(k)个环肯定是，我拆掉了(k - 2)个，留最左两个，1步拆掉最左的，这个时候我还要把这(k - 2)个环拼回去，拆一次(k - 1)
所以方案数就是(f[k] = f[k - 1] + 2 * f[k - 2] + 1)
然而太简单了，简单的都不是省选题了，所以他没让你取模= =，让你写FFT的高精乘，强行增加代码量
这个矩阵有几个位置默认是0，可以通过不对那里进行运算减小常数
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pdi pair<db, int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 1000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template <class T>
void read(T &res) {
res = 0;
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template <class T>
void out(T x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int BASE = 10;
const int len = 8;
const int MOD = 998244353, MAXL = (1 << 20);
int W[MAXL + 5];
int inc(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int mul(int a, int b) { return 1LL * a * b % MOD; }
int fpow(int x, int c) {
int res = 1, t = x;
while (c) {
if (c & 1) res = 1LL * res * t % MOD;
t = 1LL * t * t % MOD;
c >>= 1;
}
return res;
}
struct Bignum {
vector<int> v;
Bignum() { *this = 0; }
Bignum operator=(int64 x) {
v.clear();
do {
v.pb(x % BASE);
x /= BASE;
} while (x);
return *this;
}
friend Bignum operator+(const Bignum &a, const Bignum &b) {
Bignum c;
c.v.clear();
int p = 0, g = 0;
while (1) {
int x = g;
if (p < a.v.size()) x += a.v[p];
if (p < b.v.size()) x += b.v[p];
if (!x && p >= a.v.size() && p >= b.v.size()) break;
c.v.pb(x % BASE);
g = x / BASE;
++p;
}
return c;
}
friend void NTT(Bignum &a, int L, int on) {
a.v.resize(L, 0);
for (int i = 1, j = L >> 1; i < L - 1; ++i) {
if (i < j) swap(a.v[i], a.v[j]);
int k = L >> 1;
while (j >= k) {
j -= k;
k >>= 1;
}
j += k;
}
for (int h = 2; h <= L; h <<= 1) {
int wn = W[(MAXL + MAXL * on / h) % MAXL];
for (int k = 0; k < L; k += h) {
int w = 1;
for (int j = k; j < k + h / 2; ++j) {
int u = a.v[j], t = mul(w, a.v[j + h / 2]);
a.v[j] = inc(u, t);
a.v[j + h / 2] = inc(u, MOD - t);
w = mul(w, wn);
}
}
}
if (on == -1) {
int InvL = fpow(L, MOD - 2);
for (int i = 0; i < L; ++i) a.v[i] = mul(a.v[i], InvL);
}
}
friend Bignum operator*(Bignum a, Bignum b) {
Bignum c;
int t = (a.v.size() + b.v.size()), L;
L = 1;
while (L <= t) L <<= 1;
NTT(a, L, 1);
NTT(b, L, 1);
c.v.resize(L);
for (int i = 0; i < L; ++i) c.v[i] = mul(a.v[i], b.v[i]);
NTT(c, L, -1);
int64 g = 0;
for (int i = 0; i < L; ++i) {
int64 x = g + c.v[i];
c.v[i] = x % BASE;
g = x / BASE;
}
while (g) {
c.v.pb(g % BASE);
g /= BASE;
}
L = c.v.size() - 1;
while (L && c.v[L] == 0) {
c.v.pop_back();
--L;
}
return c;
}
void print() {
for (int i = v.size() - 1; i >= 0; --i) {
putchar('0' + v[i]);
}
}
} num;
struct Matrix {
Bignum f[3][3];
friend Matrix operator*(const Matrix &a, const Matrix &b) {
Matrix c;
c.f[2][2] = 1;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
c.f[i][j] = c.f[i][j] + a.f[i][k] * b.f[k][j];
}
}
}
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 3; ++k) {
c.f[2][j] = c.f[2][j] + a.f[2][k] * b.f[k][j];
}
}
return c;
}
} A, ans;
void Init() {
W[0] = 1;
W[1] = fpow(3, (MOD - 1) / MAXL);
for (int i = 2; i < MAXL; ++i) {
W[i] = mul(W[i - 1], W[1]);
}
A.f[0][0] = 1;
A.f[0][1] = 1;
A.f[1][0] = 2;
A.f[2][0] = 1;
A.f[2][2] = 1;
}
void fpow(Matrix &res, int c) {
Matrix t = A;
res = A;
--c;
while (c) {
if (c & 1) res = res * t;
t = t * t;
c >>= 1;
}
}
void Solve() {
int N;
read(N);
if (N == 1) {
puts("1");
} else if (N == 2) {
puts("2");
} else {
fpow(ans, N - 2);
num = ans.f[0][0] + ans.f[0][0] + ans.f[1][0] + ans.f[2][0];
num.print();
enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in", "r", stdin);
#endif
Init();
int T;
read(T);
while (T--) Solve();
return 0;
}