526互联

题解 ABC309Ex【Simple Path Counting Problem】

发布时间 2023-08-24 20:02:44作者: rui_er

好好玩的题。

设普通生成函数 \(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;
}