#P17744. 超级加倍
超级加倍
题目描述
在欢乐斗地主中,一共有n 种加倍卡,其中每一种都能使倍数变成原来的倍。特别的,在此我们认为底倍数为1。
当然,仅仅一次加倍是不能满足人们心中的快感的,所以腾讯推出了新的加倍方式——「超级加倍」。
定义一次「超级加倍」为进行m 次加倍操作,其中每次加倍操作可以在n 种加倍卡中任意选择一张卡进行加倍。特别的,在「超级加倍」中,每一种加倍卡的出现次数不限。
作为策划师的你,为了判断「超级加倍」的强度,你需要回答所有本质不同的「超级加倍」的倍数的和。当然,由于欢乐豆是有限的,你只需要回答对998244353 取模后的结果。
「超级加倍」A、B 本质不同定义为:存在至少一个i,使得第i
种加倍卡在A 中的出现次数不等于在B 中的出现次数。
例如,如果m=2,n=2,2 种加倍卡倍率分别为和,则共有4
种情况:
1.第一次选,第二次选,总倍率为.
2.第一次选,第二次选,总倍率为.
3.第一次选,第二次选,总倍率为.
4.第一次选,第二次选,总倍率为.
在第一种和第二种方案中,都获取了一张和一张,所以我们认为它们是本质相同的,所以上面例子中共有三种本质不同的方案,
权值和为。
注意,即便存在i、j 的加倍倍数一样,i、j 仍视作本质不同的两种加倍卡;比如在上一个例子中,如果=,本质不同的超级加倍的方案仍然有三种,而不是一种。
输入格式
从标准输入读入。
第一行两个数,分别为n、m。
第二行n 个数,第i 个表示。
输出格式
输出到标准输出。
一行一个整数,表示所有本质不同的「超级加倍」的倍数的和。
输入样例
2 3
2 3
输出样例
65
样例解释
一共有四种本质不同的超级加倍:
选择0 张第1 种卡,3 张第2 种卡,此时倍数为;
选择1 张第1 种卡,2 张第2 种卡,此时倍数为;
选择2 张第1 种卡,1 张第2 种卡,此时倍数为;
选择3 张第1 种卡,0 张第2 种卡,此时倍数为;
所以倍数和为65
数据约定
对于10%的数据,有n,m≤7。
对于30%的数据,有n,m≤100。
对于50%的数据,有n≤5,m≤。
对于70%的数据,有n≤200,m≤。
对于100%的数据,有n≤200,m≤,0<=<998244353