Description：

两个序列 $a$ 和 $b$ ，求出哪些 $k$ 满足 $b$ 循环右移 $k$ 位后 $a$ 和 $b$ 每一位对应相减 $\%998244353$ 的值可以看成是一个 $m$ 次多项式再 $1,2,\dots n$ 处的点值。

$1\leqslant n\leqslant 10^5$

Solution：

就是说 $a_i-b_{k+i\mod n}=p(i)\mod 998244353$ 其中 $p$ 是一个 $m+1$ 次多项式。

首先把 $b$ 复制一倍接在后面，然后就不用考虑循环的问题。

注意到 $p(i)-p(i-1)$ 是一个 $m$ 次多项式，也就是说 $p$ 每差分一次，次数就减一，因此我们可以把 $a-b$ 也差分 $m+1$ 次，这个其实就相当于把 $a$ 和 $b$ 分别差分再相减，那么这个时候 $a$ 和 $b$ 能匹配当且仅当 $a$ 和 $b$ 的后 $n-m-1$ 项，也就是去掉前 $m+1$ 项完全相同，这时我们可以用 $KMP$ 求解，于是现在问题就变成了如何求 $k$ 阶差分，找规律发现 $k$ 阶差分的公式为： $$ \Delta^ka_p=\sum_{i=0}^k(-1)^k\binom{k}{i}a[p-i]=\sum_{i=0}^p(-1)^k\binom{k}{i}a[p-i] $$ 这其实是个卷积，于是用 $NTT$ 计算即可。

Code：

代码就不放了