UOJ Logo Zijian Online Judge

ZOJ

#37. 小猫咪和小狐狸

统计

题目背景

小猫咪和小狐狸是好朋友。

当初贤者大人$①$收养小狐狸呢,是想要一台电脑。我们暂且抛开这个奇怪的逻辑不谈,许多年过去了,小狐狸现在很乖,当然也像当初的目标一样,善于计算,能 $O(nlogn)$ 跑LCT,能 $O(n^3)$ 跑高斯消元,能 $O(wys)$ 跑搜索。

然而小狐狸现在有一点力不从心了。听说现在,有的评测机甚至能 $O(n^2)$ 跑 $n=266666$ 的数据!于是她打算像那位贤者一样,也购置一台电脑,这样她就能跑多线程了。

然而她收养了小猫咪以后,发现自己并没有减轻任何负担。该做饭还得做饭,该写题还得写题,该颓废还是一样颓。这是由于小猫咪并不是那么善于计算,在一些日常的事物上并不能很好的帮上忙。

不过每天陪小猫咪玩耍也是一件很开心的事,所以稍微累一点也没有什么关系啦。

题目描述

贤者大人对外面的事务不管不问,只想着过自己的 $17$ 大寿。于是,小狐狸准备好了 $3$ 个月的储备粮。这些食物种类繁多,包括小鱼干,油豆腐,还有油咖喱等等,一共 $n$ 个,且它们本质不同。小猫咪最近在学组合数学,于是给小狐狸提出了这样一个问题:将这些食物全部放进 $m$ 个本质相同的盒子里,不能有空盒子,一共有多少种方案。当然,这是非常 $trivial$ 的第二类斯特林数$②$,可以用 $A(i,j)$ 表示。小狐狸很快就给出了答案。

小猫咪提出了一个新问题:定义每种方案的权值为各个盒子食物个数的乘积,求所有方案的权值和。注意要对 $998244353$ 取模。

小狐狸当然知道怎么做啦!但是她想考考你...

输入格式

一行,两个用空格隔开的整数 $n$ 和 $m$。

输出格式

一个整数,表示你求出的权值和。

样例一

input

7 4

output

2240

样例二

input

404 32

output

972205133

限制与约定

对于$10\texttt{%}$的数据,$1 \leq n \leq 10$,$1 \leq m \leq 10$

对于$40\texttt{%}$的数据,$1 \leq n \leq 500$,$1 \leq m \leq 100$

对于$70\texttt{%}$的数据,$1 \leq n \leq 5000$,$1 \leq m \leq 100$

对于$100\texttt{%}$的数据,$1 \leq n \leq 50000$,$1 \leq m \leq 1000$,$m \leq n$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

补充说明

$①$:贤者是一位17岁的女性,是小狐狸的主人。

$②$:如果你超过10分钟都对这道题没有思路,推荐阅读fpdqwq关于第二类斯特林数的简要介绍。

$③$:点击上面的"第二类斯特林数"即可跳转至fpdqwq的blog。

下载

样例数据下载