好好玩的题。
设普通生成函数 \(F_i\)，其中 \([z^k]F_i\) 表示从所有起点走到 \((i,k)\) 的方案数。特别地，\([z^k]F_1=\sum\limits_{a\in A}[a=k]\)。
注意到 \(F_i=(z^{-1}+1+z)F_{i-1}\) 几乎成立，但是在 \([z^1]F_i\) 和 \([z^M]F_i\) 处不成立。
尝试对 \(F_i\) 进行改造：
\[[z^k]F_i^\star= \begin{cases} 0,&k=0\lor k=M+1\\ [z^k]F_i,&1\le k\le M\\ -[z^{2M+2-k}]F_i,&M+2\le k\le 2M+1 \end{cases} \]考察 \(F_i^\star\) 与 \((z^{-1}+1+z)\) 的循环卷积（即 \(\bmod (z^{2M+2}-1)\) 的结果），发现由于 \(F_i^\star\) 是由 \(F_i\) 沿着 \(k=M+1\) 翻折并取相反数得到的，\([z^0]F_i^\star\) 和 \([z^{M+1}]F_i^\star\) 永远会是 \(0\)，这就防止了我们移动到网格外，从而使得循环卷积结果的系数恰好是 \(F_{i+1}^\star\) 的各项系数，即：
\[F_{i+1}^\star\equiv F_i^\star(z^{-1}+1+z)\pmod{(z^{2M+2}-1)} \]使用快速幂即可，时间复杂度 \(O(M\log M\log N)\)。
去掉封装的核心代码：（完整代码）
Poly<mod, g> qmul(const Poly<mod, g>& a, const Poly<mod, g>& b) {
Poly<mod, g> ans = a * b;
int sz = (int)ans.size();
rep(i, 2*m+2, sz-1) ans[i%(2*m+2)] += ans[i];
ans.resize(2*m+2);
return ans;
}
Poly<mod, g> qpow(Poly<mod, g> a, int k) {
Poly<mod, g> ans{1};
for(; k; k >>= 1, a = qmul(a, a)) if(k & 1) ans = qmul(ans, a);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
initPoly(N);
cin >> n >> m >> k >> l;
Poly<mod, g> a(2*m+2), b(2*m+2);
rep(i, 1, k) {
cin >> x;
++a[x];
--a[2*m+2-x];
}
b[0] = b[1] = b[2*m+1] = 1;
a = qmul(a, qpow(b, n-1));
Modint<mod, g> ans = 0;
rep(i, 1, l) {
cin >> x;
ans += a[x];
}
cout << ans << '\n';
return 0;
}