[MtOI2018]情侣？给我烧了！（加强版）
弱化版。
复读的。
我们这里有了式子：
$$f_{n,k}=\binom{n}{k}^2k!2^kd_{n-k}$$
我们需要预处理出 ${d}$：
$$d_n=\sum_{i=0}^{n}(-1)^i\binom{n}{i}^2i!2^i(2(n-i))!$$
对着这玩意凑卷积：
$$\begin{aligned}d_n
&=\sum_{i=0}^n(-1)^i\binom{n}{i}^2i!2^i(2(n-i))!
\\
&=\sum_{i=0}^{n}(-1)^i(\dfrac{n!}{(n-i)!i!})^2i!2^i(2(n-i))!
\\
&=(n!)^2\sum_{i=0}^n\dfrac{(2(n-i))!}{(n-i)!^2}\dfrac{(-2)^i}{i!}
\end{aligned}$$
这是个卷积了，但显然不可能对着这玩意跑 $5\times 10^6$ 次卷积。
定义 $H(x)=\sum_{i=0}^n\dfrac{(2(n-i))!}{(n-i)!^2}\dfrac{(-2)^i}{i!}x^i$。
设 $g_n=\dfrac{(2n)!}{n!^2}$，$p_n=\dfrac{(-2)^n}{n!}$，显然有 $f=g*p$，即 $H(x)=G(x)P(x)$。
对于 $P(x)=\sum_{i=0}\dfrac{(-2)^i}{i!}x^i=\sum_{i=0}\dfrac{(-2x)^i}{i!}=e^{-2x}$。
对于 $G(x)=\sum_{i=0}\dfrac{(2i)!}{i!^2}x^i=\sum_{i=0}\binom{2i}{i}x^i$，这个比较难处理，但我们可以知道它是 $\dfrac{1}{\sqrt{1-4x}}$。
于是我们有了 $H(x)=\dfrac{e^{-2x}}{(1-4x)^{1/2}}$。
对于这种结构，求导有奇效（基本也就求导一种方法）：
$$H’(x)=\dfrac{8xe^{-2x}}{(1-4x)^{2/3}}=\dfrac{8x}{1-4x}H(x)$$
稍微化一下：
$$H’(x)=4xH’(x)+8xH(x)$$
提出系数：
$$h_n’=4h_{n-1}’+8h_{n-1}$$
把导数还原回 $h$ 的表达：
$$(n+1)h_{n+1}=4nh_n+8h_{n-1}$$
于是我们得到递推式 $h_n=\dfrac{4(n-1)h_{n-1}+8h_{n-2}}{n}$。
然后求出 $h_n$ 后，$(n!)^2h_n=d_n$，我们的答案就可以单次 $O(1)$ 计算了。
时间复杂度 $O(n+T)$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}
using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
const ll N=5e6,mo=998244353;
ll T,n,k;
ll fac[N+5],ifac[N+5],pw2[N+5],d[N+5],inv[N+5];
namespace Aeft{
inline ll Pow(ll b,ll p) {
ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
}
inline ll C(ll n,ll m) {return (fac[n]*ifac[m]%mo)*ifac[n-m]%mo;}
}
using Aeft::Pow;using Aeft::C;
inline void Init() {
fac[0]=1;for(ll i=1;i<=N;i++) fac[i]=fac[i-1]*i%mo;
ifac[N]=Pow(fac[N],mo-2);
for(ll i=N-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mo;
pw2[0]=1;for(ll i=1;i<=N;i++) pw2[i]=pw2[i-1]*2ll%mo;
inv[1]=1;for(ll i=2;i<=N;i++) inv[i]=inv[mo%i]*(mo-mo/i)%mo;
d[0]=1;d[1]=0;
for(ll i=2;i<=N;i++) {
d[i]=((4*(i-1)%mo)*d[i-1]%mo+8*d[i-2]%mo)*inv[i]%mo;
}
}
int main() {
T=read();Init();
while(T--) {
n=read();k=read();
ll tmp=C(n,k);
tmp=tmp*tmp%mo;
tmp=tmp*fac[k]%mo;
tmp=tmp*pw2[k]%mo;
tmp=tmp*d[n-k]%mo;
tmp=tmp*fac[n-k]%mo;
tmp=tmp*fac[n-k]%mo;
writeln(tmp);
}
return 0;
}
|