#1326. 「MtOI2019」埋骨于弘川

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Quank123Wip

题目描述

在幻想乡,西行寺 幽幽子 (Yuyuko) 是一个以贪吃著名的亡灵,她拥有操纵死亡的能力。

Yuyuko 通过外界的式神——电脑,对 OI 进行了深刻的研究 ,她发现了一些惊人的事实:

  • OIer 们放弃了太多其他同学们拥有的东西,在题海中寻求自己的梦想。

  • 但是 AFO 的 OIer 们,跟死亡又有什么区别呢?他们或许已经失去了自己的梦想……

这时幽幽子发现,天空中飘舞的樱花组成了两个整数 n k 。于此同时,在樱花树下,出现了一个函数 f(x,y) 的描述:

f(x,y) = \begin{cases} 2 & , x=1 \\ 2^x& , 2\le x \le 42,y = 0 \\ \prod\limits_{i=1}^{42} f(x-i,y)^i & , x \ge 43,y = 0 \\ f(x-1,y)f(x,y-1) & , x\ge 2,y \ge 1\end{cases}

幽幽子想让你计算出 f(n,k) \bmod 998244353 ,她认为这个函数象征着 OIer 们……

输入格式

两个整数 n,k

输出格式

一个正整数 f(n,k) \bmod 998244353

样例

样例输入 1

1 1926

样例输出 1

2

样例解释 1

根据定义, f(1,1926)=2

样例输入 2

23 3

样例输出 2

509581943

样例输入 3

1919 810

样例输出 3

252250482

数据范围与提示

子任务

本题采用捆绑测试。

子任务编号 分值 n k
1 7 \leq 1000 1\leq k\leq 1000
2 11 \leq 10^{18} =0
3 13 =1
4 29 0\leq k\leq 1000
5 40 0\leq k\leq 30000

题目来源

迷途之家 2019 联赛 (MtOI2019) T6

出题人:NaCly_Fish

验题人:Imagine

此题稍有卡常,请注意优化代码常数。