#P12394. 「RiOI-6」神曲

    ID: 13830 远端评测题 2500ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>多项式洛谷原创O2优化快速数论变换 NTT拉格朗日反演洛谷比赛

「RiOI-6」神曲

题目背景

安慰一个伤心的人,真的好困难呢……

在好友最需要自己的时候,明明有很多话可说,却只会“好惨”“拍拍”“抱抱”什么的,真的很让人自责啊。

如果萝卜能让所有人对感情认真起来,像她这样被伤害的人,是不是就会少一些呢?

题目描述

定义一个长度为 nn,值域为 VV 的二元组序列 (li,ri)i=1n(l_i,r_i)^n_{i=1} 是好的,当且仅当:

  • 1in,1liriV\forall 1\le i\le n, 1\le l_i\le r_i\le V
  • $\forall 1\le i<j\le n, (l_j\le l_i\le r_i\le r_j)\lor(r_j < l_i)\lor(r_i < l_j)$。

换句话说,每个二元组代表一个区间,且对于所有 i<ji<j,要么 [li,ri][l_i,r_i][lj,rj][l_j,r_j] 包含,要么 [li,ri][l_i,r_i][lj,rj][l_j,r_j] 没有交集。

给定 n,mn,m。请对 V=1,2,,mV=1,2,\cdots,m,求出有多少个长度为 nn,值域为 VV 的二元组序列是好的。答案对 998244353998244353 取模。

输入格式

一行两个正整数 n,mn,m

输出格式

一行 mm 个非负整数,表示答案。

1 5
1 3 6 10 15
2 2
1 7
10 20
1 2047 261625 10391745 210766920 738437852 751995961 367882293 626598267 990684424 32946479 746153195 309367626 577393442 149727732 683395486 756615148 203162153 948422841 561114284
100 20
1 766755082 570047877 716144748 321097835 123137643 571618454 644127872 879655648 371687313 984928153 761377418 790560387 887056207 799077157 156396768 647907515 242209960 978001146 356334941

提示

【样例解释】

对于样例 11,满足在值域内的区间显然有 V(V+1)2\frac{V(V+1)}2 种。所以 V=1,,5V=1,\cdots,5 时答案为 1,3,6,10,151,3,6,10,15

对于样例 22

V=1V=1 时,显然只有一种好的序列:[(1,1),(1,1)][(1,1),(1,1)]
V=2V=2 时:好的序列有以下 77 种:

  • [(1,1),(2,2)][(1,1),(2,2)]
  • [(2,2),(1,1)][(2,2),(1,1)]
  • [(1,1),(1,1)][(1,1),(1,1)]
  • [(2,2),(2,2)][(2,2),(2,2)]
  • [(1,1),(1,2)][(1,1),(1,2)]
  • [(2,2),(1,2)][(2,2),(1,2)]
  • [(1,2),(1,2)][(1,2),(1,2)]

对于样例 3,43,4,暂时不能给你一个明确的答复。

【数据范围】

本题开启捆绑测试。

子任务 分数 nn\le mm\le
11 55 1010
22 2×1052\times10^5 22
33 2020 5050
44 5×1035\times10^3
55 1010 4×1044\times10^4
66 2020 10510^5
77 2×1052\times10^5

对于 100%100\% 的数据,1n,m2×1051\le n,m\le 2\times10^5

请注意常数因子对程序运行效率的影响。