#P6140. LYK loves sequence

    ID: 6440 传统题 4000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-递推计数普通生成函数多项式求逆多项式牛顿迭代NTT

LYK loves sequence

题目描述

给定一个 1,2,…,n1,2,\dots,n 的排列 aa。如果对每个切分位置 1≤i<n1\le i<n,都存在下标 u≤i<vu\le i<v 使得 au>ava_u>a_v,则称 aa 为美妙排列。

求美妙排列的数量,对 998244353998244353 取模。

输入格式

第一行一个正整数 TT,表示询问组数。

接下来 TT 行,每行一个正整数 nn。

输出格式

输出 TT 行,每行一个整数,表示相应询问的答案。

样例

1
3
3

美妙排列为 (2,3,1)(2,3,1)、(3,1,2)(3,1,2)、(3,2,1)(3,2,1)。

数据范围

  • 对于 20% 的数据,n≤10n\le10。
  • 对于 40% 的数据,n≤1000n\le1000。
  • 对于 80% 的数据,1≤n,T≤1000001\le n,T\le100000。
  • 其余 20% 的数据满足 T=1T=1、n=2000000n=2000000。

原赛 PDF。本站的比较条件按原样例和现有评测数据校订。