# 牛客网暑期ACM多校训练营（第八场） B Filling pools

• 2018-08-11
• 48
• 0

## 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.

3

6

4

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)}

50

## Sample Output:

780401176

### 题目链接

n ans
1 1
2 2
3 6
4 22

f_{n}=f_{n-1}+\sum_{k=0}^{n-1}{f_{k}\times f_{n-1-k}}

f(n)\times(n+1)=(6n-3)\times f(n-1)-(n-2)\times f(n-2)