感谢强大 alpha！！1【1】

· · 个人记录

我们要求的是：

\begin{aligned} G(x)&=\sum_{i\geq 0}(i+n-m)!(-1)^{m-i}x^i\\ G'(x)&=\sum_{i\geq 1}i(i+n-m)!(-1)^{m-i}x^{i-1} \end{aligned}

考虑凑 \sum\limits_{i\geq 1}(i+n-m)!(-1)^{m-i}x^i：

\begin{aligned} -x((n-m+1)G(x)+xG'(x))&=\sum\limits_{i\geq 1}(i+n-m)!(-1)^{m-i}x^i\\ &=G(x)+(-1)^{m-1}(n-m)! \end{aligned}

因此：

\begin{aligned} x^2G'(x)&=-[(n-m+1)x+1]G(x)+(-1)^{m}(n-m)!\\ F^2G'(F)&=-[(n-m+1)F+1]G(F)+(-1)^{m}(n-m)!\\ F^2\frac{[G(F)]'}{F'}&=-[(n-m+1)F+1]G(F)+(-1)^{m}(n-m)!\\ \end{aligned}

考虑到 F=\frac{x+x^2}{1-x},F'=\frac{(1+2x)(1-x)+(x+x^2)}{(1-x)^2}，带入：

\begin{aligned} F^2\frac{[G(F)]'}{F'}&=-[(n-m+1)F+1]G(F)+(-1)^{m}(n-m)!\\ (x+x^2)^2\frac{[G(F)]'}{(1+2x)(1-x)+(x+x^2)}&=-\frac{(n-m+1)(x+x^2)+1-x}{1-x}G(F)+(-1)^{m}(n-m)!\\ \end{aligned}

于是：

(x+x^2)^2(1-x)[G(F)]'=\\ -[(n-m+1)(x+x^2)+1-x][1+2x-x^2]G(F)+(-1)^{m}(n-m)!(1-x)(1+2x-x^2)\\

后面的最高项是 x^3，是用来赋初值的。剩下的对比系数：

\begin{aligned} [x^m](x+x^2)^2(1-x)[G(F)]'&=-[x^m][(n-m+1)(x+x^2)+1-x][1+2x-x^2]G(F)\\ \end{aligned}

别以为初值就是子问题！注意 m 是不变的！

const int N = 1e7 + 5;

int n, m, L[6], R[5], H[6], G[N];

signed main () {
    IN (n), IN (m);

    // get L
    L[1] = 1;
    L[2] = 1;
    L[3] = mod - 1;
    L[4] = mod - 1;

    // get R
    R[0] = 1;
    R[1] = n - m;
    R[2] = n - m + 1;
    rep (i, 2, 0) {
        pls (R[i + 2], mul (mod - 1, R[i]));
        pls (R[i + 1], mul (2, R[i]));
    }

    // get fac[n - m]
    int pot = (n - m) / B, buf = rec[pot];
    lep (i, pot * B + 1, n - m) buf = mul (buf, i);

    int fix = qpow (mod - R[0], mod - 2);
    int ori = mul (((m & 1) ? mod - 1 : 1), buf);

    lep (i, 0, m) {
        lep (j, 1, min (4, i)) {
            pls (G[i], mul (L[j], mul (i - j, G[i - j])));
            pls (G[i], mul (R[j], G[i - j]));
        }

        if (i <= 3) sub (G[i], mul ((i == 2 ? mod - 3 : 1), ori));
        G[i] = mul (fix, G[i]);
    }

    printf ("%d\n", G[m]);
    return 0;
}