我们要求的是:
\[\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;
}
标签:frac,21,int,题解,end,22.11,mul,aligned,mod
From: https://www.cnblogs.com/qiulyqwq/p/16913272.html