继续扮演
题目描述
给定两个长度为 n 的非负整数序列 a0,…,an−1 和 b0,…,bn−1。
定义 b 序列的 k 变换为循环左移 k 位,得到序列
bi′=b(k+i)modn(0≤i<n).
求出哪些 0≤k<n 满足:存在一个次数不超过 m 的多项式
P(x)=cmxm+cm−1xm−1+⋯+c1x+c0,
使对所有 0≤i<n,均有
P(i)≡ai−bi′(mod998244353).
多项式系数在模 998244353 意义下选取,允许最高若干项的系数为 0。
输入格式
第一行两个整数 n,m,表示序列长度和多项式次数上限。
第二行 n 个非负整数 a0,…,an−1。
第三行 n 个非负整数 b0,…,bn−1。
输出格式
第一行一个非负整数 cnt,表示满足条件的 k 的数量。
接下来 cnt 行,每行一个整数,按升序输出所有满足条件的 k。
数据范围
所有数据满足 1≤n≤105,0≤m≤109,0≤ai,bi<998244353。
| 子任务 |
分值 |
附加限制 |
| 1 |
7 |
n−1≤m |
| 2 |
13 |
n≤10,m≤10 |
| 3 |
29 |
n≤100,m≤100 |
| 4 |
5 |
m=0 |
| 5 |
11 |
m≤1 |
| 6 |
17 |
m≤100 |
| 7 |
18 |
无特殊限制 |