洛谷 4931 「MtOI2018」情侣？给我烧了！『加强版』

学了学 EI 的做法……
总算是看懂了。

设 n 对情侣都不和睦的方案数为 fn，则恰有 k 对情侣和睦的方案数为 (nk)2fn−kk!2k

两个组合数分别是从 n 对情侣里选 k 对，从 n 排里选 k 排；k! 是这 k 对情侣的排列方案；2k 是情侣两个人互相换位置。

那么枚举和睦情侣的对数有 n∑k=0(nk)2fn−kk!2k=(2n)!

众所周知 EGF 的卷积会附带一个组合数，而上式中除了组合数以外的都显然是卷积的形式。
于是可以如法炮制 EGF，设计一种新的生成函数： F(x)=∞∑n=0fnxn(n!)2

这样的话卷积就可以有两个组合数了。

那么我们考虑上式中除了 F 以外的两个数列 ∞∑n=0n!2nxn(n!)2=∞∑n=02nxnn!=e2x∞∑n=0(2n)!xn(n!)2=∞∑n=0(−12n)(−4)nxn=(1−4x)−1/2

即 e2xF(x)=(1−4x)−1/2F(x)=e−2x(1−4x)−1/2

求个导看看 F′(x)=8xe−2x(1−4x)−3/2=8x1−4xF(x)(1−4x)F′(x)=8xF(x)F′(x)=4xF′(x)+8xF(x)

又因为 (∞∑n=0fnxn(n!)2)′=∞∑n=0(fnxn(n!)2)′=∞∑n=1fnnxn−1(n!)2=∞∑n=0(n+1)−1fn+1xn(n!)2xF′(x)=∞∑n=0(n+1)−1fn+1xn+1(n!)2=∞∑n=1nfnxn(n!)2xF(x)=∞∑n=0fnxn+1(n!)2=∞∑n=1n2fn−1xn(n!)2

于是 (n+1)−1fn+1=4nfn+8n2fn−1fn+1=4n(n+1)fn+8n2(n+1)fn−1(n≥1)

初值为 f0=1,f1=0。

代码：

#include <cstdio>
using namespace std;
const int N = 5e6;
const int mod = 998244353;
int T,n,k;
int fac[N + 5],ifac[N + 5];
int f[N + 5];
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int main()
{
    f[0] = fac[0] = 1;
    for(register int i = 2;i <= N;++i)
        f[i] = (4LL * (i - 1) % mod * i % mod * f[i - 1] % mod + 8LL * (i - 1) % mod * (i - 1) % mod * i % mod * f[i - 2] % mod) % mod;
    for(register int i = 1;i <= N;++i)
        fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[N] = fpow(fac[N],mod - 2);
    for(register int i = N;i;--i)
        ifac[i - 1] = (long long)ifac[i] * i % mod;
    scanf("%d",&T);
    for(;T;--T)
        scanf("%d%d",&n,&k),printf("%lld\n",(long long)fac[n] * fac[n] % mod * ifac[k] % mod * ifac[n - k] % mod * ifac[n - k] % mod * fpow(2,k) % mod * f[n - k] % mod);
}