QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100
[+1]

# 146. 常系数齐次线性递推

Statistics

已知一个整数序列 a0,a1, 满足以下线性递推关系:

\forall i \geq n, a_i \equiv \sum_{k=1}^n c_ka_{i-k} \pmod {998\,244\,353}

给定 a_0,a_1,\cdots,a_{n-1}c_1,c_1,\cdots,c_{n}k,你想要计算 a_k 取模 998\,244\,353 的值。

输入格式

输入的第一行包含两个整数 n,k

接下来一行,包含 n 个整数 a_0, a_1, \cdots, a_{n-1}

接下来一行,包含 n 个整数 c_1, c_1, \cdots, c_{n}

输出格式

输出一行一个整数,表示答案。

样例数据

样例 1 输入

3 10
2 5 3
1 4 6

样例 1 输出

58953

样例 2 输入

5 75789123
4 6 1 3 8
2 5 0 0 9

样例 2 输出

71403842

样例 3 输入

6 1999999
2 3 4 5 6 7
0 0 0 0 0 0

样例 3 输出

0

子任务

对于所有数据,1 \leq n \leq 10^50 \leq k \leq 10^90 \leq a_i,c_i < 998\,244\,353

子任务编号 n \leq 分值
1 100 5
2 1\,000 20
3 5\,000 15
4 20\,000 5
5 30\,000 15
6 40\,000 5
7 60\,000 10
8 80\,000 10
9 10^5 15