#PQJ1860x9651. QOJ 1860_9651

    ID: 2739 传统题 2500ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测动态规划数学

QOJ 1860_9651

标题: 又一个欧拉数问题 - Problem - QOJ.ac

#9651. 又一个欧拉数问题

Statistics

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。