题目大意
你在一个有 n 个点的环上，环上点按逆时针顺序标号为 0 到 n-1。你一开始在 0 号点。
你在每一回合可以使用 k 种传送中的一种，第 i 种传送会将你按逆时针方向移动 a[i] 个点。
有 m 个限制条件，对于每个限制条件 (xi, yi)，要求不能在第 xi 步之后在 yi 号点上。
你要求出经过 L 步之后在 0 号点的方案数模 998244353。
n <= 65536 且 n 为 2 的幂。
L <= 1e9， m <= 15， k <= 1e5
时限 2s。
题解
L 这么大。。。于是我们想到矩阵乘法经典套路。
设 f[i] 表示当前在 i 这个位置的方案数。我们根据 k 种传送把转移矩阵构出来好像就行了。
限制的话很好处理，假设有个限制是 (xi, yi)，那就在乘 xi 次之后，把 f[yi] 赋值为 0。
但是这个转移矩阵太大了。
于是发现我们不需要矩阵，只需要一个 01 序列就行了。比如我们有一种传送是 a[i]，那就在序列 A 的第 a[i] 位标为 1。然后用 f 和 A 做一次循环卷积，这就相当于一次转移了。
处理限制跟上面相同，即相当于把 L 分成很多段。时间复杂度 $O(mlog ~Ln~log~n)$
发现过不了。。。
这时候就可以用另一个经典套路了。
对于卷积，我们先做一次 DFT，然后把 n 个点值分别幂 L 次，再做逆 DFT。
可以证明，这样拆开来幂，跟合起来幂是一样的结果。具体请访问 YxuanwKeith的博客。
这样时间就是 $O(m(log~n+n~log~L))$
tips
循环卷积时，如果 n 是 2 的幂，可以直接把数组大小开成 n 做普通卷积。