CF1153F [* hard]
看上去挺有意思的一道题。
有一段长为 (L) 的线段，有 (N) 个区间，左右端点在 ([0,L)) 间均匀随机（可能不是整数）
求在这条线段上，期望被至少 (K) 段区间覆盖的线段的长度，对 (998244353) 取模。
(N,Kle 2000,Lle 10^9)
(
m Sol:)
先论证一个简单的结论，在一 ([0,1)) 上随机选两个数得到的线段期望长度为 (frac{1}{3})
可以考虑每个点被覆盖的概率，此点被覆盖当且仅当两个数不在其同一边，那么对于 (x)，其被覆盖的概率为 (1-x^2-(1-x)^2=2x-2x^2)
那么我们计算的期望其实就是 (f(x)) 的积分，于是 (int_{0}^1 f(x)=x^2-frac{2x^3}{3})，代入 (x=1) 得到 (frac{1}{3})
本题中，类似的，我们先将长度为 (L) 的线段视为长度 (1)，那么答案乘以 (L) 即可。
设 (f(x)) 为点 (x) 被覆盖至少 (K) 次的概率，我们可以从一个简单的角度下手并考虑，设 (g(x,k,p)) 表示以点 (x) 为基准，当前其被被覆盖了 (k) 次，已经用了 (p) 条线段的概率，那么我们有：
[g(x,k,p)=g(x,k-1,p-1) imes dotsm+g(x,k,p-1) imes dotsm
]
转移本质上是在做多项式运算，如果暴力转移，然后对点值进行操作并选择插值还原，就可以得到一个 (mathcal O(N^2K)) 的做法了。
然而事实上这个多项式我们可以直接计算出来，不妨设 (P(x)) 表示对于一组线段，(x) 被覆盖的概率，那么我们有：
[f(x)=sum_{i=K}^{N} inom{N}{i} P(x)^i(1-P(x))^{N-i}
]
由于 (P(x)) 为关于 (x) 的二次函数，所以 (f(x)) 为关于 (x) 的 (2N) 次多项式。我们随便找 (2N+1) 个点值就可以解决本题了。
至此，通过拉格朗日插值与积分的结论，我们可以得到一个 (mathcal O(N^2)) 的做法。
注意到：
[F(x)=sum_{i=1}^n y_i prod_{i
e j}frac{(x-x_j)}{(x_i-x_j)}
]
计算分子的连乘，这里 (mathcal O(n^2))，接下来我们暴力计算多项式除以短多项式，这里 (mathcal O(n))，需要算 (mathcal O(n)) 次，复杂度为 (mathcal O(n^2))
注意到我们知道点值，那么我们是可以简单得到下降幂多项式的系数序列。
如果知道下降幂的系数序列，那么又可以优雅的暴力转普通幂多项式。
展开是没有前途的，而且真的没有前途，所以我们大力积分：
先给一个结论：
[B(x,y)=int_0^1 t^x(1-t)^ydt=frac{x!y!}{(x+y+1)!}
]
证明：
考虑计算
[egin{aligned}
&int g'(x)f(x)
\&=g(x)f(x)-int g(x)f'(x)
end{aligned}]
证明：
注意到前者为：
[egin{aligned}
&g(x)f(x)=int (g'(x)f(x)+f'(x)g(x))
\&=int g'(x)f(x)+int g(x)f'(x)
end{aligned}]
于是得证。
接着注意到：
[egin{aligned}
&B(a,b)=int_0^1 x^a(1-x)^b dx
end{aligned}]
我们构造 (g(x)=frac{x^{a+1}}{a+1})，那么 (x^a=g'(x))，然后令 (f(x)=(1-x)^b)
于是有：
[egin{aligned}
&B(a,b)=int_0^1 g'(x)f(x)
\& B(a,b)=Big(g(1)f(1)-g(0)f(0)Big)-int_0^1 g(x)f'(x)
\& B(a,b)=-int_0^1 frac{x^{a+1}}{a+1}f'(x)
\& B(a,b)=int_0^1 frac{x^{a+1}}{a+1} b(1-x)^{b-1}
\& B(a,b)=frac{b}{a+1}int_0^1 x^{a+1}(1-x)^{b-1}
end{aligned}]
接下来我们设 (n=a+b)，那么有：
[B(k,n-k)=frac{n-k}{k+1}int_0^1 x^{k+1}(1-x)^{n-k-1}
]
注意到：
[B(k,n-k)=frac{n-k}{k+1}B(k+1,n-k-1)
]
注意到 (B(n,0)=int_0^1 x^n=frac{1}{n+1})
于是可以得到 (B(n-1,1)=frac{1}{n(n+1)})
类似递推得到 (B(k,n-k)=frac{(n-k)!}{(n+1)^{underline{n-k+1}}}=frac{(n-k)!k!}{(n+1)!})
代入 (B(a,b)) 中得到 (B(a,b)=frac{a!b!}{(a+b+1)!})
事实上，注意到 (P(x)=2x(1-x))
[egin{aligned}
&int_0^1 dxcdot f(x)=int dxcdot sum_{i=K}^{N} inom{N}{i} P(x)^i(1-P(x))^{N-i}
\&=int_0^1 dxcdot sum_{i=K}^{N} inom{N}{i} (2x)^i(1-x)^i(1-(2x)(1-x))^{N-i}
\&=sum_{i=K}^N inom{N}{i} int_0^1 dx cdot (2x)^i(1-x)^isum_j^{N-i}inom{N-i}{j}(-1)^j(2x)^j(1-x)^j
\&=sum_{i=K}^N inom{N}{i} int_0^1 dxsum_j^{N-i}inom{N-i}{j}(-1)^{j}(2x)^{i+j}(1-x)^{i+j}
\&=sum_{i=K}^N inom{N}{i} sum_j^{N-i} inom{N-i}{j}(-1)^j2^{i+j} int_0^1 dxcdot x^{i+j}(1-x)^{i+j}
end{aligned}]
等等，这个式子，是不是就是我们的前置知识？！
所以我们得到：
[egin{aligned}
&=sum_{i=K}^N inom{N}{i} sum_j^{N-i} inom{N-i}{j}(-1)^j2^{i+j} frac{((i+j)!)^2}{(2(i+j)+1)!}
\&=sum_{k=K}^N frac{(k!)^2 imes 2^k}{(2k+1)!}sum_{i=K}^N sum_{j}^{N-i} [i+j=k] inom{N}{i}inom{N-i}{j}(-1)^j
\&=sum_{k=K}^N frac{(k!)^2 imes 2^k}{(2k+1)!}sum_{i=K}^N sum_{j}^{N-i} [i+j=k] inom{N}{i+j}inom{i+j}{j}(-1)^j
\&=sum_{k=K}^N frac{(k!)^2 imes 2^kinom{N}{k}k!}{(2k+1)!}sum_{i=K}^N sum_{j}^{N-i} [i+j=k] frac{1}{j!i!}(-1)^j
end{aligned}]
分别卷积即可。