QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 1024 MB Total points: 100
[+7]

# 9651. 又一个欧拉数问题

统计

题目描述

给定 k 以及系数序列 w0w2k11。定义一个 nk 阶排列 p 的权值 val(p)=nk+1i=1wf(pi,pi+1,,pi+k1) 其中 f(a1,a2,,ak)=k1i=12i1[ai<ai+1] 给定 n,计算所有 n 阶排列的权值和 mod

输入格式

第一行两个整数 n, k

第二行 2^{k - 1} 个整数,第 i 个整数表示 w_{i-1}

输出格式

一行一个整数,表示答案 \bmod , 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 \le k = 分值
1 10 4 5
2 20 4 10
3 10^5 2 5
4 100 3 10
5 4000 3 10
6 4 \times 10^4 3 15
7 10^5 3 5
8 2000 4 10
9 4 \times 10^4 4 10
10 10^5 4 20

对于所有数据:2 \le k \le 4k \le n \le 10^50 \le w_i < 998244353