#PQJ1860x9651. QOJ 1860_9651
QOJ 1860_9651
标题: 又一个欧拉数问题 - Problem - QOJ.ac
#9651. 又一个欧拉数问题
The problem was used in the following contests:
题目描述
给定 k 以及系数序列 w0∼w2k−1−1。定义一个 n≥k 阶排列 p 的权值
val(p)=∏i=1n−k+1wf(pi,pi+1,…,pi+k−1)
其中
f(a1,a2,…,ak)=∑i=1k−12i−1[ai<ai+1]
给定 n,计算所有 n 阶排列的权值和 mod998244353。
输入格式
第一行两个整数 n,k。
第二行 2k−1 个整数,第 i 个整数表示 wi−1。
输出格式
一行一个整数,表示答案 mod,998244353。
样例
样例 #1
样例输入 #1
3 2
1 2
样例输出 #1
13
样例 #2
样例输入 #2
5 3
1 2 3 4
样例输出 #2
1875
样例 #3
样例输入 #3
6 4
1 2 3 4 5 6 7 8
样例输出 #3
68850
数据范围
本题使用捆绑测试,你只有通过一个子任务的所有测试点,才能获得这个子任务的分数。
子任务编号 n≤ k= 分值 1 10 4 5 2 20 4 10 3 105 2 5 4 100 3 10 5 4000 3 10 6 4×104 3 15 7 105 3 5 8 2000 4 10 9 4×104 4 10 10 105 4 20
对于所有数据:2≤k≤4,k≤n≤105,0≤wi<998244353。