牛客网暑期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.

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

数列前几项为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)以外都是2倍的关系,所以可以使用这个公式计算。

AC代码:

评论

还没有任何评论,你来说两句吧