【P5401 [CTS2019] 珍珠】题解
MoYuFang
·
·
个人记录
本题解参考 cmd 大佬的题解。
时间复杂度为 O(D)，是严格的线性，目前 2022.3.11 是最优解。
为了方便先改变一下记号，记 n 为颜色数（随机变量的范围，也就是 D），L 为珍珠数（随机变量个数），m 为瓶子数。
至少装满 m 个瓶子相当于至少配对 m 对珍珠。
容易证明，以下两种情况是平凡的
-
-
所以接下来讨论的情况都是 0\le L-2m\le n-2。
设有 i 种颜色出现了奇数个珍珠（称作奇颜色），有 n-i 种颜色出现了偶数个珍珠（称作偶颜色）。
这样仅有 i 个珍珠是孤立的，其它珍珠一定能配对。
所以配对的个数就是 \displaystyle \frac{L-i}{2}，至少配对 m 对珍珠相当于 i\le L-2m。
也就是说只要满足 0\le i\le L-2m，方案一定合法。
使用 \text{EGF}，奇颜色和偶颜色的 \text{EGF} 可分别表示为
\begin{aligned}
\frac{e^x+e^{-x}}{2}\\
\frac{e^x-e^{-x}}{2}
\end{aligned}
所以有 i 种奇颜色，n-i 种偶颜色的情况就可以表示为
L![x^L]\left(\frac{e^x+e^{-x}}{2}\right)^{n-i}\left(\frac{e^x-e^{-x}}{2}\right)^{i}
枚举奇颜色的个数，最终答案就是
ans=\sum_{i=0}^{L-2m}{n\choose i}L![x^L]\left(\frac{e^x+e^{-x}}{2}\right)^{n-i}\left(\frac{e^x-e^{-x}}{2}\right)^{i}
化简一番
\begin{aligned}
ans&=\frac{1}{2^n}\sum_{i=0}^{L-2m}{n\choose i}L^{n-i}(e^x-e^{-x})^{i}\\
&=\frac{1}{2^n}\sum_{i=0}^{L-2m}{n\choose i}L![x^L]\sum_{j=0}^{n-i}\sum_{k=0}^{i}{n-i\choose j}{i\choose k}(-1)^{i-k}e^{jx}e^{(i+j-n)x}e^ke^{(k-i)x}\\
&=\frac{1}{2^n}\sum_{i=0}^{L-2m}{n\choose i}L![x^L]\sum_{j=0}^{n-i}\sum_{k=0}^{i}{n-i\choose j}{i\choose k}(-1)^{i-k}e^{(2j+2k-n)x}\\
&=\frac{1}{2^n}\sum_{i=0}^{L-2m}{n\choose i}\sum_{j=0}^{n-i}\sum_{k=0}^{i}{n-i\choose j}{i\choose k}(-1)^{i-k}(2j+2k-n)^{L}\\
&=\frac{1}{2^n}\sum_{i=0}^{L-2m}{n\choose i}\sum_{r=0}^{n}(2r-n)^{L}\sum_{k=0}^{r}{n-i\choose r-k}{i\choose k}(-1)^{i-k}\\
&=\frac{1}{2^n}\sum_{i=0}^{L-2m}{n\choose i}\sum_{r=0}^{n}(2r-n)^{L}[x^r](x-1)^{i}(x+1)^{n-i}\\
&=\frac{1}{2^n}\sum_{r=0}^{n}(2r-n)^{L}[x^r]\sum_{i=0}^{L-2m}{n\choose i}(x-1)^{i}(x+1)^{n-i}\\
\end{aligned}
不妨设 k=L-2m，生成函数 f(x) 满足
f(x)=\sum_{i=0}^{k}{n\choose i}(x-1)^{i}(x+1)^{n-i}\tag{*0}
所以
ans=\frac{1}{2^n}\sum_{r=0}^{n}(2r-n)^Lf[r]
于是问题的关键在于求解函数 f(x)。
因为 k\neq n，很难通过二项式定理等普通的方法去掉 f(x) 中的求和式，于是我们尝试通过求导得出 f(x) 的封闭形式（也就是去掉了求和符号的等式），再通过此求出 f(x) 的递推式。
然而 f(x) 的形式较复杂，我们先求出两个形式更简单的生成函数的封闭形式，以此为基础再求出 f(x) 的封闭形式。
首先设
g(x)=\sum_{i=0}^{k}{n\choose i}A(x)^i\tag{*1}
求导得
g'(x)=A'(x)\sum_{i=0}^{k}{n\choose i}iA(x)^{i-1}\tag{*2}
变换形式得
\begin{aligned}
g'(x)&=A'(x)\sum_{i=1}^{k}{n\choose i-1}(n-i+1)A(x)^{i-1}\\
&=nA'(x)\sum_{i=1}^{k}{n\choose i-1}A(x)^{i-1}-A'(x)\sum_{i=1}^{k}{n\choose i-1}(i-1)A(x)^{i-1}\\
&=nA'(x)\sum_{i=0}^{k-1}{n\choose i}A(x)^{i}-A'(x)\sum_{i=0}^{k-1}{n\choose i}iA(x)^{i}\\
\end{aligned}\tag{*3}
将 (\text{*1}) 与 (\text{*2}) 综合到 (\text{*3}) 上，得出
g'(x)
=nA'(x)\left(g(x)-{n\choose k}A(x)^{k}\right)-\left(A(x)g'(x)-A'(x){n\choose k}kA(x)^{k}\right)
整理后得到
nA'(x)g(x)-(A(x)+1)g'(x)={n\choose k}(n-k)A'(x)A(x)^k\tag{*4}
再设
h(x)=\sum_{i=0}^{k}{n\choose i}A(x)^iB(x)^{n-i}
我们现在求出 h(x) 的封闭形式。
\frac{h(x)}{B(x)^{n}}=\sum_{i=0}^{k}{n\choose i}\left(\frac{A(x)}{B(x)}\right)^i\tag{*5}
注意到 (\text{*5}) 的形式与 (\text{*1}) 相同，我们直接利用 (\text{*4}) 的结果。
\left(\frac{h(x)}{B(x)^{n}}\right)'=\frac{h'(x)B(x)-nh(x)B'(x)}{B(x)^{n+1}}\\
\left(\frac{A(x)}{B(x)}\right)'=\frac{A'(x)B(x)-A(x)B'(x)}{B(x)^2}
将上面两个求导式带入 (\text{*4})，同时在等式左右两边乘上 B(x)^{n+2} 后得
n(A'B-AB')h-(A+B)(h'B-nhB')={n\choose k}(n-k)(A'B-AB')A^kB^{n-k}
式子太长了，就先省略 (x) 了。
整理后得到
nB(A'+B')h-B(A+B)h'={n\choose k}(n-k)(A'B-AB')A^kB^{n-k}
两边同时除以 B 得到最终形式
n(A'+B')h-(A+B)h'={n\choose k}(n-k)(A'B-AB')A^kB^{n-k-1}\tag{*6}
重新对照 h(x) 的表达式 (\text{*5}) 和 f(x) 的表达式 (\text{*0}) 得到
A(x)=x-1,\ B(x)=x+1
带入 (\text{*6}) 得
nf(x)-xf'(x)={n\choose k}(n-k)(x-1)^k(x+1)^{n-k-1}\tag{*7}
于是我们去掉了求和号，得到了 f(x) 的封闭形式。
然而 (\text{*7}) 仍不能很好的帮助我们求出 f(x) 的递推式，还需要更进一步。
设 a>0,b>0\ (a,b\in\mathbb{Z})，生成函数 p(x) 满足
p(x)=(x-1)^a(x+1)^b
则有
\begin{aligned}
p'(x)=\frac{a}{x-1}p(x)+\frac{b}{x+1}p(x)\\
x^2p'(x)-p'(x)=(a+b)xp(x)+(a-b)p(x)
\end{aligned}
令 a=k,\ b=n-k-1，得到
x^2p'(x)-p'(x)=(n-1)xp(x)+(2k+1-n)p(x)
这显然可以求出递推式，于是当 i\ge 2 时有
\begin{aligned}[]
[x^{i-1}](x^2p'(x)-p'(x))=[x^{i-1}]((n-1)xp(x)+(2k+1-n)p(x))\\
(i-2)p[i-2]-ip[i]=(n-1)p[i-2]+(2k+1-n)p[i-1]\\
p[i]=\frac{1}{i}(n-2k-1)p[i-1]-\frac{1}{i}(n-i+1)p[i-2]
\end{aligned}\tag{*8}
直接观察 p(x) 的定义是，可以得到递推的边界条件为
p[0]=(-1)^k,\ p[1]=(-1)^k(n-2k-1)
由 (\text{*7}) 知
nf(x)-xf'(x)={n\choose k}(n-k)p(x)
所以当 0\le i\le n 时有
(n-i)f[i]={n\choose k}(n-k)p[i]
对照 (\text{*8}) 得，当 2\le i\le n-1 时有
f[i]=\frac{n-i+1}{i(n-i)}\left((n-2k-1)f[i-1]-(n-i+2)f[i-2]\right)\tag{*9}
ps: 多么丑陋的式子啊！
递推的边界条件是
\begin{aligned}
&f[0]=\frac{g[0]}{n}=(-1)^k{n-1\choose k}\\
&f[1]=\frac{g[1]}{n-1}=(-1)^k\frac{n-k}{n-1}{n\choose k}
\end{aligned}\tag{*10}
其次，直接观察 f(x) 定义式 (\text{*0}) 可得
\begin{aligned}
f[n]&=[x^n]\sum_{i=0}^{k}{n\choose i}(x-1)^{i}(x+1)^{n-i}\\
&=\sum_{i=0}^{k}{n\choose i}
\end{aligned}\tag{*11}
利用 (\text{*9}),(\text{*10}),(\text{*11})，我们可以以 O(n) 求出 f[i]\ (0\le i\le n)。
回看答案的计算式
ans=\frac{1}{2^n}\sum_{r=0}^{n}(2r-n)^Lf[r]
设 t(i)=i^L\ (0\le i\le n)，注意到 t 是完全积性函数，对素数进行快速幂，用线性筛可以以 O(n\log n/\ln n)=O(n) 预处理出 t(i)。
因此可以 O(n) 求出 ans。
以下是代码。
```cpp
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <assert.h>
using namespace std;
#define re register
#define sf scanf
#define pf printf
#define nl() putchar('\n')
#define ll unsigned long long
#define db double
#define _for(i, a, b) for(re int i = (a); i < (b); ++i)
#define _rfor(i, a, b) for(re int i = (a); i <= (b); ++i)
#define maxn 100005
#define mod 998244353ll
int rdnt(){
re int x = 0, sign = 1;
re char c = getchar();
while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (c ^ 48), c = getchar();
return x * sign;
}
int n, L, m, k, pcnt = 0,
f[maxn],
t[maxn],
prime[maxn],
iv[maxn],
fct[maxn],
ivf[maxn];
bool vis[maxn];
int fp(re int x, re int n){re int y=1;for(;n;x=(ll)x*x%mod,n>>=1)if(n&1)y=(ll)x*y%mod;return y;}
int get_inv(re int a){ return fp(a, mod-2); }
int C(re int n, re int m){ return (ll)fct[n]*ivf[m]%mod*ivf[n-m]%mod; }
void init(re int n){
t[1] = iv[1] = fct[0] = fct[1] = ivf[0] = ivf[1] = 1; t[0] = 0;
_rfor(i, 2, n){
if (!vis[i]) prime[++pcnt] = i, t[i] = fp(i, L), iv[i] = get_inv(i);
fct[i] = (ll)fct[i-1]*i%mod;
ivf[i] = (ll)ivf[i-1]*iv[i]%mod;
for(re int j = 1; j <= pcnt && i*prime[j] <= n; ++j){
vis[i*prime[j]] = true;
iv[i*prime[j]] = (ll)iv[i]*iv[prime[j]]%mod;
t[i*prime[j]] = (ll)t[i]*t[prime[j]]%mod;
if (i%prime[j] == 0) break;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
#endif
n = rdnt(), L = rdnt(), m = rdnt(), k = L-2*m;
if (k > n-2){ pf("%d\n", fp(n, L)); return 0; }
if (k < 0){ pf("0\n"); return 0; }
init(n);
f[0] = (ll)C(n-1, k)%mod;
if (k&1) f[0] = (mod-f[0])%mod;
f[1] = (ll)C(n, k)*(n-k)%mod*(n-2*k-1+mod)%mod*iv[n-1]%mod;
if (k&1) f[1] = (mod-f[1])%mod;
_rfor(i, 0, k) f[n] = (f[n] + C(n, i))%mod;
_rfor(i, 2, n-1){
f[i] = (
(ll)(mod+n-2*k-1)*f[i-1]%mod -
(ll)(n-i+2)%mod*f[i-2]%mod + mod
)%mod*iv[n-i]%mod*iv[i]%mod*(n-i+1)%mod;
}
re int ans = 0, j;
_rfor(i, 0, n){
j = 2*i>=n ? t[2*i-n] : (L&1 ? mod-t[n-2*i] : t[n-2*i]);
//assert(j == fp((mod+2*i-n)%mod, L));
ans = (ans + (ll)j*f[i]%mod)%mod;
}
ans = (ll)fp(iv[2], n)*ans%mod;
pf("%d\n", ans);
return 0;
}
```