题目
传送门 to CF：这是 C F _ G Y M 102798 E \rm CF\_GYM102798E CF_GYM102798E 一道原题。
题目描述
有 n n n 个随从，第 i i i 个的生命值为 a i a_i ai 。现在你会连续攻击 m m m 次，每次等概率地选择一个仍然存活的随从，并对它造成 1 1 1 的伤害（使其生命值减小 1 1 1）。当一个随从的生命值降为 0 0 0 时，它立刻死亡（不再存活）。
现在问你，死亡随从数量的期望是多少。对 998244353 998244353 998244353 取模。
数据范围与提示
n ≤ 15 , m ≤ 200 , a i ≤ 200 n\le 15,\;m\le 200,\;a_i\le 200 n≤15,m≤200,ai≤200，保证 m ≤ ∑ i a i m\le\sum_{i}a_i m≤∑iai 。
思路壹
我考场上就想的这种做法。但是因为很难打，并且复杂度不太对，就放弃了……
出师不利
经典题目 猎人杀，大家肯定都做过。还是用这种方法：认为死掉的随从仍然可以被攻击，只是它无效而已。
不难发现，这里有两个要素：有效攻击次数；总攻击次数。前者是满足题目条件用的，后者是计算概率用的。
那么我们可以很轻松地写出一个二元生成函数，用 x x x 代表有效攻击， y y y 代表总攻击：
F i ( x , y ) = ∑ b ≥ 0 x min ( a i , b ) ⋅ y b b ! ⋅ ( 1 n ) b F_i(x,y)=\sum_{b\ge 0}x^{\min(a_i,b)}\cdot \frac{y^b}{b!}\cdot\left({1\over n}\right)^b Fi(x,y)=b≥0∑xmin(ai,b)⋅b!yb⋅(n1)b
显然 y y y 应当是指数型，因为 y y y 的合并是需要用组合数的。它计算的是排列。
可以稍微化简一下，得到
F i ( x , y ) = x a i ( e y / n − ∑ j < a i y j n j ⋅ j ! ) + ∑ j < a i x j y j n j ⋅ j ! F_i(x,y)=x^{a_i}\left(e^{y/n}-\sum_{j<a_i}\frac{y^j}{n^j\cdot j!}\right)+\sum_{j<a_i}\frac{x^jy^j}{n^j\cdot j!} Fi(x,y)=xai(ey/n−j<ai∑nj⋅j!yj)+j<ai∑nj⋅j!xjyj
二元生成函数的卷积，大家都会做，就是 f a M + b f_{aM+b} faM+b 为 x a y b x^{a}y^b xayb 的系数，然后卷积，其中 ⌊ M − 1 2 ⌋ \lfloor\frac{M-1}{2}\rfloor ⌊2M−1⌋ 是 y y y 的次数最大值。考虑到 x x x 的范围是 m m m 而 y y y 的范围是 ∑ a i ≤ n a \sum a_i\le na ∑ai≤na，复杂度是
O ( n m a log n m a ) \mathcal O(nma\log nma) O(nmalognma)
那么，我们只需要尽力求出
P ( x , y ) = ∏ i F i ( x , y ) = ∑ j = 0 n A j ( x , y ) ⋅ e y j / n P(x,y)=\prod_i F_i(x,y)=\sum_{j=0}^{n}A_{j}(x,y)\cdot e^{yj/n} P(x,y)=i∏Fi(x,y)=j=0∑nAj(x,y)⋅eyj/n
然后我们求 ∑ j = 0 + ∞ [ x m y j ] j ! ⋅ P ( x , y ) \sum_{j=0}^{+\infty}[x^my^j]\;j!\cdot P(x,y) ∑j=0+∞[xmyj]j!⋅P(x,y) 就毫不费力了。毕竟 e y j / n = ∑ t = 0 + ∞ ( y j ) t n t ⋅ t ! e^{yj/n}=\sum_{t=0}^{+\infty}\frac{(yj)^t}{n^t\cdot t!} eyj/n=∑t=0+∞nt⋅t!(yj)t 嘛。枚举 A j ( x , y ) A_j(x,y) Aj(x,y) 中 y y y 的次数 k k k，乘 e y j / n e^{yj/n} eyj/n 得 ∑ t = 0 + ∞ j t y t + k n t ⋅ t ! \sum_{t=0}^{+\infty}\frac{j^t y^{t+k}}{n^t\cdot t!} ∑t=0+∞nt⋅t!jtyt+k，第 j j j 项乘 j ! j! j! 求和得到
∑ t = 0 + ∞ j t ⋅ ( t + k ) ! n t ⋅ t ! \sum_{t=0}^{+\infty}\frac{j^t\cdot(t+k)!}{n^t\cdot t!} t=0∑+∞nt⋅t!jt⋅(t+k)!
我们有理由相信，这是可以 O ( log k ) \mathcal O(\log k) O(logk) 计算的。那么统计答案的总复杂度就是 O ( n 2 a log n a ) \mathcal O(n^2a\log na) O(n2alogna) 了。
怎么求 A j ( x , y ) A_j(x,y) Aj(x,y) 呢？考虑直接 N T T \tt NTT NTT 的话，要计算 n 2 n^2 n2 组二元卷积，所以复杂度是
O ( n 3 m a log n m a ) \mathcal O(n^3ma\log nma) O(n3malognma)
这是概率，现在要求期望，只需要钦定某个随从必然被干掉。即只取 b ≥ a i b\ge a_i b≥ai 的情况。用算出的 P ( x , y ) P(x,y) P(x,y) 减去后面的 ∑ j < a i x j y j n j ⋅ j ! \sum_{j<a_i}{x^jy^j\over n^j\cdot j!} ∑j<ainj⋅j!xjyj 就行了。这个就预处理前缀、后缀，然后三者相乘。
容易发现，复杂度已经受不了了……
工业革命
原因在于 n , m n,m n,m 并不对等，二者数据范围相距悬殊。这么小的 n n n，肯定引导我们往 2 n ∼ 3 n 2^n\sim 3^n 2n∼3n 左右去思考。
考虑枚举 b ≥ a i b\ge a_i b≥ai 的集合 S S S，因为此时 ∑ j < a i x j y j n j ⋅ j ! \sum_{j<a_i}\frac{x^jy^j}{n^j\cdot j!} ∑j<ainj⋅j!xjyj 满足 x , y x,y x,y 次数相同，就不需要使用二元生成函数了。一元生成函数的卷积，复杂度就可以明显优化下来。
具体而言，我们只需要求
[ y m − ∑ j ∈ S a j ] ∏ j ∉ S ( ∑ b < a j y b n b ⋅ b ! ) [y^{m-\sum_{j\in S}a_j}]\prod_{j\notin S}\left(\sum_{b<a_j}\frac{y^b}{n^b\cdot b!}\right) [ym−∑j∈Saj]j∈/S∏⎝⎛b<aj∑nb⋅b!yb⎠⎞
这是被 x x x 的次数限制住了的。然后再求
∏ j ∈ S ( e y / n − ∑ b < a j y b n b ⋅ b ! ) \prod_{j\in S}\left(e^{y/n}-\sum_{b<a_j}\frac{y^b}{n^b\cdot b!}\right) j∈S∏⎝⎛ey/n−b<aj∑nb⋅b!yb⎠⎞
注意这里 y y y 的次数，有一个很强劲的限制：它是钦定了被干掉的随从，所以 ∑ a ≤ m \sum a\le m ∑a≤m，所以 y y y 的最高次数是 m m m 而不是 n a na na 。
但是我们有一个很高妙的做法：要知道，系数为 1 1 1 的指数型生成函数，求导 是不会大变样的。我们试试，对 y y y 求导：
( e y / n − ∑ b < a j y b n b ⋅ b ! ) ′ = e y / n n − ∑ b = 1 a j − 1 y b − 1 n b ⋅ ( b − 1 ) ! \left(e^{y/n}-\sum_{b<a_j}\frac{y^b}{n^b\cdot b!}\right)'=\frac{e^{y/n}}{n}-\sum_{b=1}^{a_j-1}\frac{y^{b-1}}{n^b\cdot(b-1)!} ⎝⎛ey/n−b<aj∑nb⋅b!yb⎠⎞′=ney/n−b=1∑aj−1nb⋅(b−1)!yb−1
记左式（原式）为 F j ( y ) F_j(y) Fj(y)，右式则为 F j ′ ( y ) F_j'(y) Fj′(y)，不难发现
F j ( y ) = n ⋅ F j ′ ( y ) − y a j − 1 n a j − 1 ⋅ ( a j − 1 ) ! ⇒ F j ′ ( y ) = F j ( y ) n + y a j − 1 n a j ⋅ ( a j − 1 ) ! F_j(y)=n\cdot F_j'(y)-\frac{y^{a_j-1}}{n^{a_j-1}\cdot(a_j-1)!}\\ \Rightarrow F'_j(y)=\frac{F_j(y)}{n}+\frac{y^{a_j-1}}{n^{a_j}\cdot(a_j-1)!} Fj(y)=n⋅Fj′(y)−naj−1⋅(aj−1)!yaj−1⇒Fj′(y)=nFj(y)+naj⋅(aj−1)!yaj−1
那么，我们将目标式子 ∏ j ∈ S F j ( y ) \prod_{j\in S}F_j(y) ∏j∈SFj(y) 求导试一试：
[ ∏ j ∈ S F j ( y ) ] ′ = ∑ x ∈ S F x ′ ( y ) ∏ j ∈ S j ≠ x F j ( y ) = ∑ x ∈ S [ F x ( y ) n + y a x − 1 n a x ⋅ ( a x − 1 ) ! ] ∏ j ∈ S j ≠ x F j ( y ) = ∏ j ∈ S F j ( y ) + ∑ x ∈ S y a x − 1 n a x ⋅ ( a x − 1 ) ! ∏ j ∈ S j ≠ x F j ( y ) \begin{aligned} &\left[\prod_{j\in S}F_j(y)\right]' =\sum_{x\in S}F_x'(y)\prod_{j\in S}^{j\ne x}F_j(y)\\ &=\sum_{x\in S}\left[\frac{F_x(y)}{n}+\frac{y^{a_x-1}}{n^{a_x}\cdot(a_x-1)!}\right]\prod_{j\in S}^{j\ne x}F_j(y)\\ &=\prod_{j\in S}F_j(y)+\sum_{x\in S}\frac{y^{a_x-1}}{n^{a_x}\cdot(a_x-1)!}\prod_{j\in S}^{j\ne x}F_j(y) \end{aligned} ⎣⎡j∈S∏Fj(y)⎦⎤′=x∈S∑Fx′(y)j∈S∏j=xFj(y)=x∈S∑[nFx(y)+nax⋅(ax−1)!yax−1]j∈S∏j=xFj(y)=j∈S∏Fj(y)+x∈S∑nax⋅(ax−1)!yax−1j∈S∏j=xFj(y)
怎么从导数反推回原式呢？考虑到
[ A j ( y ) ⋅ e y j / n ] ′ = A j ( y ) ⋅ j ⋅ e y j / n n + A j ′ ( y ) ⋅ e y j / n \left[A_j(y)\cdot e^{yj/n}\right]'=A_j(y)\cdot \frac{j\cdot e^{yj/n}}{n}+A_j'(y)\cdot e^{yj/n} [Aj(y)⋅eyj/n]′=Aj(y)⋅nj⋅eyj/n+Aj′(y)⋅eyj/n
那么，当我们知道左式，又知道 A j ( y ) A_j(y) Aj(y) 的 k k k 次项时，我们就可以推出 A j ′ ( y ) A'_j(y) Aj′(y) 的 k k k 次项，进而知道 A j ( y ) A_j(y) Aj(y) 的 k + 1 k+1 k+1 次项。
对应到这个式子上，我们对于每个 e y j / n e^{yj/n} eyj/n 单独求系数。此时，我们考虑去计算右式的 k k k 次项，这当然是 O ( ∣ S ∣ ) \mathcal O(|S|) O(∣S∣) 的，然后就求出了 k + 1 k+1 k+1 次项。所以总复杂度
O ( n 2 m ⋅ 2 n ) \mathcal O(n^2m\cdot 2^n) O(n2m⋅2n)
新能源
这是另一个求解 ∏ ( e y / n − ∑ y b n b ⋅ b ! ) \prod(e^{y/n}-\sum\frac{y^b}{n^b\cdot b!}) ∏(ey/n−∑nb⋅b!yb) 的方法，由 T i w - A i r - O A O \sf Tiw\text-Air\text-OAO Tiw-Air-OAO 提供。
它同时也解决了第一个式子 ∏ ∑ y b n b ⋅ b ! \prod\sum\frac{y^b}{n^b\cdot b!} ∏∑nb⋅b!yb，可能更高妙。
考虑再枚举一次 e y / n − ∑ b < a j y b n b ⋅ b ! e^{y/n}-\sum_{b<a_j}\frac{y^b}{n^b\cdot b!} ey/n−∑b<ajnb⋅b!yb 中，究竟是二者的哪一个，就可以直接得知 e e e 的指数了。那么我们得到的就是
∑ T ⫅ S ( − 1 ) ∣ T ∣ e y ( ∣ S ∣ − ∣ T ∣ ) / n ∏ j ∈ T ( ∑ b < a j y b n b ⋅ b ! ) \sum_{T\subseteqq S}(-1)^{|T|}e^{y(|S|-|T|)/n}\prod_{j\in T}\left(\sum_{b<a_j}\frac{y^b}{n^b\cdot b!}\right) T⫅S∑(−1)∣T∣ey(∣S∣−∣T∣)/nj∈T∏⎝⎛b<aj∑nb⋅b!yb⎠⎞
你以为它退化成了 3 n 3^n 3n 。注意到 ∣ T ∣ |T| ∣T∣ 相等时， e e e 的次数是固定的，考虑合并它们。定义
Z S , k ( y ) = ∑ T ⫅ S ∣ T ∣ = k ∏ j ∈ T ( ∑ b < a j y b n b ⋅ b ! ) Z_{S,k}(y)=\sum_{T\subseteqq S}^{|T|=k}\prod_{j\in T}\left(\sum_{b<a_j}\frac{y^b}{n^b\cdot b!}\right) ZS,k(y)=T⫅S∑∣T∣=kj∈T∏⎝⎛b<aj∑nb⋅b!yb⎠⎞
还用上面的法子，求导，不难发现
F T ′ ( y ) = n F T ( y ) − ∑ x ∈ T y a x − 1 n a x − 1 ⋅ ( a x − 1 ) ! F T − { x } F_T'(y)=nF_T(y)-\sum_{x\in T}\frac{y^{a_x-1}}{n^{a_x-1}\cdot(a_x-1)!}F_{T-\{x\}} FT′(y)=nFT(y)−x∈T∑nax−1⋅(ax−1)!yax−1FT−{x}
这里 F T F_T FT 就是你想的那个意思。进而
Z S , k ′ ( y ) = ∑ T ⫅ S ∣ T ∣ = k [ n F T ( y ) − ∑ x ∈ T ⋯ ] Z_{S,k}'(y)=\sum_{T\subseteqq S}^{|T|=k}\left[nF_T(y)-\sum_{x\in T}\cdots\right] ZS,k′(y)=T⫅S∑∣T∣=k[nFT(y)−x∈T∑⋯]
（由于后面那一坨太长，我就不写出来啦。直接用上面的式子替换得到的嘛。）
= n Z S , k ( y ) − ∑ x ∈ S y a x − 1 n a x − 1 ⋅ ( a x − 1 ) ! Z S − { x } , k − 1 ( y ) =nZ_{S,k}(y)-\sum_{x\in S}\frac{y^{a_x-1}}{n^{a_x-1}\cdot(a_x-1)!}Z_{S-\{x\},k-1}(y) =nZS,k(y)−x∈S∑nax−1⋅(ax−1)!yax−1ZS−{x},k−1(y)
同理，这个是 O ( n ) \mathcal O(n) O(n) 转移，一共 O ( n m 2 n ) \mathcal O(n m2^n) O(nm2n) 个状态，复杂度仍然是
O ( n 2 m ⋅ 2 n ) \mathcal O(n^2m\cdot 2^n) O(n2m⋅2n)
应该也可以过吧？但不是最优解。
思路贰
考场上被我直接否定的做法：“概率的分母在变，还是要不得。”——《论 O n e I n D a r k \sf OneInDark OneInDark 为什么弱》
留坑待填
考虑 k k k 个死掉的随从，按照时间顺序是第 x 1 , x 2 , x 3 , … , x k x_1,x_2,x_3,\dots,x_k x1,x2,x3,…,xk 次攻击时被打死的。
那么这个方案的概率一定是
( 1 n − k ) m − x k ∏ i = 0 k − 1 ( 1 n − i ) x i + 1 \left(\frac{1}{n-k}\right)^{m-x_k}\prod_{i=0}^{k-1}\left(\frac{1}{n-i}\right)^{\large x_{i+1}} (n−k1)m−xki=0∏k−1(n−i1)xi+1
与每次具体是哪个随从受伤无关。有了这一点，我们考虑先勾勒出这个轮廓，然后再确定究竟是哪些随从。
用 f ( i , S ) f(i,S) f(i,S) 表示，考虑了前 i i i 次攻击，集合 S S S 中的随从死掉了，所有这种方案的概率和。如果下一步没有某个随从的死亡，直接乘 1 n − ∣ S ∣ \frac{1}{n-|S|} n−∣S∣1 就行；如果有随从死亡，考虑在前面分配给这个随从 a j − 1 a_j-1 aj−1 次攻击（因为这一次攻击是肯定打到它的）。所以
f ( i + 1 , S ) = f ( i , S ) n − ∣ S ∣ + ∑ j ∈ S ( i − ∑ x ∈ S x ≠ j a x a j − 1 ) f ( i , S − { j } ) n − ∣ S ∣ + 1 f(i+1,S)=\frac{f(i,S)}{n-|S|}+\sum_{j\in S}{i-\sum_{x\in S}^{x\ne j}a_x\choose a_j-1}\frac{f(i,S-\{j\})}{n-|S|+1} f(i+1,S)=n−∣S∣f(i,S)+j∈S∑(aj−1i−∑x∈Sx=jax)n−∣S∣+1f(i,S−{j})
显然这是 O ( n m ⋅ 2 n ) \mathcal O(nm\cdot 2^n) O(nm⋅2n) 的。这就比 思路壹 少了一个 n n n 。
折半填坑
但是 f f f 数组是答案吗？当然不是。因为它还留着很多洞。
再定义 g ( i , S ) g(i,S) g(i,S) 表示，把 i i i 次攻击分配给 S S S 集合中的随从，使得每个人都没有死亡，方案数的和。这个其实就是一个背包。真正的答案是
∑ S ⫅ U ∣ S ∣ ⋅ f ( m , S ) ⋅ g ( m − ∑ x ∈ S a x , U − S ) \sum_{S\subseteqq\Bbb U}|S|\cdot f(m,S)\cdot g\left(m-\sum_{x\in S}a_x,\Bbb U-S\right) S⫅U∑∣S∣⋅f(m,S)⋅g(m−x∈S∑ax,U−S)
直接求这个背包，复杂度是 O ( m 2 2 n ) \mathcal O(m^22^n) O(m22n)，上天了！国集大佬 C h a r l o t t e ′ s S p a c e \sf Charlotte's\;Space Charlotte′sSpace 写了 N T T \tt NTT NTT 优化，还是过不去。
注意到这样一个事实： g ( i , S ) g(i,S) g(i,S) 其实是 S S S 集合内的元素对应的指数型生成函数的乘积的 i i i 次项，即 g ( i , S ) = i ! ⋅ [ y i ] ∏ j ∈ S ( ∑ b < a j y b b ! ) g(i,S)=i!\cdot [y^i]\prod_{j\in S}(\sum_{b<a_j}\frac{y^b}{b!}) g(i,S)=i!⋅[yi]∏j∈S(∑b<ajb!yb)，然后我们求的是 G ( U − S ) G(\Bbb U-S) G(U−S) 的某一项。
两个多项式相乘，只取一项时，复杂度是 O ( m ) \mathcal O(m) O(m) 的。于是乎，我们 m e e t - i n - m i d d l e \tt meet\text-in\text-middle meet-in-middle，就把复杂度优化到了
O ( m 2 2 n + m 2 n ) \mathcal O(m^2\sqrt{2^{n}}+m2^{n}) O(m22n+m2n)
另：此处也可以使用 T i w - A i r - O A O \sf Tiw\text-Air\text-OAO Tiw-Air-OAO 的求导大法。它更通用。
代码
这里就给出 思路贰 的代码了，毕竟好写。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MaxM = 200;
const int MaxN = 16;
const int Mod = 998244353;
int dp[MaxM+1][1<<MaxN];
int inv[MaxN+1], c[MaxM+1][MaxM+1];
int a[1<<MaxN], cnt[1<<MaxN];const int HalfN = 8;
int g[2][1<<HalfN][MaxM+1];
int getG(int S,int m){int L = S&((1<<HalfN)-1);int R = S>>HalfN, ans = 0;for(int i=0; i<=m; ++i)ans = (ans+1ll*g[0][L][m-i]*g[1][R][i]%Mod*c[m][i])%Mod;return ans;
}int main(){int n = readint(), m = readint();for(int i=(inv[1]=1)+1; i<=n; ++i)inv[i] = (0ll+Mod-Mod/i)*inv[Mod%i]%Mod;for(int i=0; i<=m; ++i)for(int j=c[i][0]=1; j<=i; ++j)c[i][j] = (c[i-1][j-1]+c[i-1][j])%Mod;for(int i=0; i<n; ++i)a[1<<i] = readint();for(int S=1; S!=(1<<n); ++S){a[S] = a[S^(S&-S)]+a[S&-S];cnt[S] = cnt[S^(S&-S)]+1;}dp[0][0] = 1; // nothing ever happensfor(int i=1; i<=m; ++i)for(int S=0; S<(1<<n); ++S){if(a[S] > i) continue; // impossibledp[i][S] = 1ll*dp[i-1][S]*inv[n-cnt[S]]%Mod;for(int j=0; j<n; ++j) if(S>>j&1)dp[i][S] = (dp[i][S]+1ll*dp[i-1][S^(1<<j)]*c[i-1-a[S^(1<<j)]][a[1<<j]-1]%Mod*inv[n-cnt[S]+1])%Mod;}g[0][0][0] = g[1][0][0] = 1;for(int d=0; d<2; ++d)for(int S=1,id; S<(1<<HalfN); ++S){for(id=0; !(S>>id&1); ++id);g[d][S][0] = 1; // for surefor(int i=1; i<=m; ++i)for(int j=0; j<a[1<<(id+d*HalfN)]&&j<=i; ++j)g[d][S][i] = (g[d][S][i]+1ll*c[i][j]*g[d][S^(1<<id)][i-j])%Mod;}int ans = 0;for(int S=1; S<(1<<n); ++S){if(a[S] > m) continue; // impossibleans = (ans+1ll*cnt[S]*dp[m][S]%Mod*getG((1<<n)-1-S,m-a[S]))%Mod;}printf("%d\n",ans);return 0;
}
