Description:

Niuniu is interested in a game. The goal of the game is to fill a pool with water. The pool is a n*n square. Every cell of the pool is either empty or filled with water. All the cells are empty at the beginning. NiuNiu has to choose exactly one cell in each row and each column to fill with water. Every moment, for every cell, if there’re at least 2 adjacent cells filled with water, the cell will be filled with water too. Note that two cells are adjacent if and only if they share a side. Niuniu wants to calculate the number of ways to fill the pool. The answer may be large, so you only need to calculate it modulo 998244353.

Input:

There’s only one number n in the only row. (1 ≤ n < 262144)

Output:

You should print exactly one number, which is the answer modulo 998244353.

Sample Input:

3

Sample Output:

6

Sample Input:

4

Sample Output:

22

Hint:

There’re 2 ways which cannot fill the pool.

{(1,3),(2,1),(3,4),(4,2)}

{(1,2),(2,4),(3,1),(4,3)}

Sample Input:

50

Sample Output:

780401176

题目链接

先推出前几个数和结果的关系

n ans
1 1
2 2
3 6
4 22

之后丢入OEIS(手动滑稽…并不会正解)

可以看到这道题的正解是施罗德数,但是按照

f n = f n 1 + k = 0 n 1 f k × f n 1 k f_{n}=f_{n-1}+\sum_{k=0}^{n-1}{f_{k}\times f_{n-1-k}} fn=fn1+k=0n1fk×fn1k

递推公式暴力肯定会超时,在网上搜索“施罗德数”可以查到“超级卡特兰数”,其递推公式为:

f ( n ) × ( n + 1 ) = ( 6 n 3 ) × f ( n 1 ) ( n 2 ) × f ( n 2 ) f(n)\times(n+1)=(6n-3)\times f(n-1)-(n-2)\times f(n-2) f(n)×(n+1)=(6n3)×f(n1)(n2)×f(n2)

数列前几项为1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463……

仔细观察可以看到这个数列和施罗德数除了 f ( 1 ) f(1) f(1)以外都是 2 2 2倍的关系,所以可以使用这个公式计算。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 5;
const int mod = 998244353;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	ll n;
	while (read(n)) {
		if (n == 1) {
			print(1);
			continue;
		}
		n++;
		ll f[maxn] = {1, 1}, inv[maxn] = {1, 1};
		for (int i = 2; i <= n; ++i) {
			inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		}
		for (int i = 2; i <= n; ++i) {
			f[i] = ((6 * i - 3) * f[i - 1] % mod - (i - 2) * f[i - 2] % mod + mod) % mod * inv[i + 1] % mod;
		}
		print(f[n - 2] * 2 % mod);
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}