#P7409. 继续扮演

    ID: 7423 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理高阶差分多项式与生成函数卷积转化NTT字符串KMP构造与建模复制数组处理环组合数学阶乘逆元预处理CF2500

继续扮演

继续扮演

题目描述

给定两个长度为 nn 的非负整数序列 a0,…,an−1a_0,\ldots,a_{n-1} 和 b0,…,bn−1b_0,\ldots,b_{n-1}。

定义 bb 序列的 kk 变换为循环左移 kk 位,得到序列

bi′=b(k+i) mod n(0≤i<n).b'_i=b_{(k+i)\bmod n}\qquad(0\le i<n).

求出哪些 0≤k<n0\le k<n 满足:存在一个次数不超过 mm 的多项式

P(x)=cmxm+cm−1xm−1+⋯+c1x+c0,P(x)=c_mx^m+c_{m-1}x^{m-1}+\cdots+c_1x+c_0,

使对所有 0≤i<n0\le i<n,均有

P(i)≡ai−bi′(mod998244353).P(i)\equiv a_i-b'_i\pmod{998244353}.

多项式系数在模 998244353998244353 意义下选取,允许最高若干项的系数为 00。

输入格式

第一行两个整数 n,mn,m,表示序列长度和多项式次数上限。

第二行 nn 个非负整数 a0,…,an−1a_0,\ldots,a_{n-1}。

第三行 nn 个非负整数 b0,…,bn−1b_0,\ldots,b_{n-1}。

输出格式

第一行一个非负整数 cntcnt,表示满足条件的 kk 的数量。

接下来 cntcnt 行,每行一个整数,按升序输出所有满足条件的 kk。

数据范围

所有数据满足 1≤n≤1051\le n\le10^5,0≤m≤1090\le m\le10^9,0≤ai,bi<9982443530\le a_i,b_i<998244353。

子任务 分值 附加限制
1 7 n−1≤mn-1\le m
2 13 n≤10,m≤10n\le10,m\le10
3 29 n≤100,m≤100n\le100,m\le100
4 5 m=0m=0
5 11 m≤1m\le1
6 17 m≤100m\le100
7 18 无特殊限制