CF Round#698 Div1. Nezzar and Chocolate Bars

前言

这就是大道至简吗。。

为什么和某ZJOI开关一样，到最后就是个背包。。

题目大意：

给定$n,K$和一些棍子长度为$l_i(i\in [1,n])$（实数！）

每次随机选择一根棍子，概率与$l_i$成正比，然后随机分裂成两段（实数！）

一直分裂，直到每根棍子$l_i\leq K$，求期望分裂次数

根据题意容易归纳一个更直观的模型：

把这些$l_i$排在数轴上，初始时，点集为$0,l_1,l_1+l_2,\ldots$

每次随机在数轴上撒一个点，直到点集中相邻两点距离$\leq K$为止

考虑从简单情况入手

n=1

单棍情况，设长度为$L$，考虑期望的简单等价变换

$\displaystyle E(\text{条件第一次成立操作数})=\sum_{i=0}^{\infty} P(i次操作条件未成立)$

设$P_n$为操作$n$次成立（不是恰好）的概率 (变量名重了不要介意)

设$n$次操作后的点集排列之后为$X_i$，其中$X_0=0,X_{n+1}=L$

我们要求$\forall i\in[1,n+1],Z_i=X_i-X_{i-1}\leq K$，考虑用一个二项式反演来解决这个计算

设$W=\lfloor \frac{L} {K}\rfloor$

$\displaystyle P_n=\frac{1} {L^n}\sum_{i=0}^{W} (-1)^i\binom{n+1} {i}(L-iK)^n$

其意义即为从分成的$n+1$个$Z_i$中选择$i$个强制不合法，然后剩下的随意分布，由此计算概率

一般情形

考虑一样的期望转概率，设$p_m$为$m$次完成的概率，$q_m=1-p_m$

$\displaystyle q_m=\sum_{j_1+j_2+\cdots +j_n=m} \frac{m!} {j_1!j_2!\cdots j_n!}\prod (\frac{l_i} {\sum l_k})^{j_i}P_{i,j_i}$

显然这里考虑用$\text{EGF}$积的形式来表示，设$S=\sum l_i$

回到上一步，这里我们对于$i,l_i$计算其$P_n$加上$\frac{l_i} {S}$系数的$\text{EGF}$，沿用上面的$L=l_i$

$\displaystyle F_i(x)=\text{EGF(P)}=\sum_{n\ge 0}\frac{1} {n!}(\frac{L} {S})^n\sum_{i=0}^W(-1)^{i}\binom{n+1} {i}(1-i\frac{K} {L})^{n}x^n$

$\displaystyle F_i(x)=\sum_{n\ge 0}\frac{1} {n!}\sum_{i=0}^W(-1)^{i}\binom{n+1} {i}(\frac{L-iK} {S})^{n}x^n$

设$\displaystyle u=\frac{L-iK} {S}x$

$\displaystyle F_i(x)=\sum_{i=0}^W\frac{(-1)^{i} } {i!}\sum_{n\ge i-1}\frac{n+1} {(n+1-i)!}u^n$

令$n’=n+1-i$，$n=n’+i-1$，将$n’$带入

$\displaystyle F_i(x)=\sum_{i=0}^W\frac{(-1)^{i} } {i!}\sum_{n\ge 0}\frac{n+i} {n!}u^{n+i-1}$

将$n,i$拆开

$\displaystyle F_i(x)=\sum_{i=0}^W \frac{(-1)^{i} } {i!}(u^{i}\sum_{n\ge 0}\frac{1} {n!}u^{n}+u^{i-1}\sum_{n\ge 0}\frac{i} {n!}u^{n})$

$\displaystyle F_i(x)=\sum_{i=0}^W \frac{(-1)^{i} } {i!}(u^{i}+iu^{i-1})e^u$

容易发现我们需要多项式是$F(x)=e^x-\prod F_i(x)$

最终$F(x)$的每一项，都会是$x^k e^{cx}$的形式

其中$e^u$中的$u$总是$\frac{1} {S}(L-iK)x$，合并之后$L$之和总是存在，记录$\sum i$即可，为$O(S)$

而每项要么是$u^ie^u$要么是$u^{i-1}e^u$，可以考虑记录一下$u^{i-1}e^u$出现的次数，为$O(n)$

我们的多项式项数是$O(nS)$的

最终我们还需要对于每一项计算答案

我们要计算$\displaystyle \sum_{n\ge 0}n![x^n]F(x)$，考虑形如$x^ke^{cx}$一项的贡献

$\displaystyle \sum_{n\ge k}nx^n=\sum_{n\ge k}\frac{n!} {(n-k)!}c^{n-k}=k!\sum_{n\ge 0}\binom{n+k} {n}c^{n}$

由于$\displaystyle \binom{n+k} {n}=(-1)^{n}\binom{-k-1} {n}$

带入广义二项式定理得到

$\displaystyle k!\sum_{n\ge 0}\binom{n+k} {n}c^{n}=k!(1-c)^{-k-1}$

根据是否用$\text{NTT}$优化，复杂度会有所不同

over.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;

typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=1<<11|10,P=998244353;

int n,m,k;
ll qpow(ll x,ll k=P-2) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}

int rev[N],I[N],J[N];
typedef vector <int> V;
void Init(){
    rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
    I[N-1]=qpow(J[N-1]);
    drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
    int R=1,c=-1;
    while(R<=n) R<<=1,c++;
    rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
    return R;
}
void NTT(int n,V &a,int f) {
    static int e[N>>1];
    rep(i,0,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int i=e[0]=1;i<n;i<<=1) {
        ll t=qpow(f==1?3:(P+1)/3,(P-1)/i/2);
        for(int j=i-2;j>=0;j-=2) e[j+1]=(e[j]=e[j>>1])*t%P;
        for(int l=0;l<n;l+=i*2) {
            for(int j=l;j<l+i;++j) {
                int t=1ll*e[j-l]*a[j+i]%P;
                a[j+i]=a[j]-t,Mod2(a[j+i]);
                a[j]+=t,Mod1(a[j]);
            }
        }
    }
    if(f==-1) {
        ll Inv=1ll*I[n]*J[n-1]%P;
        rep(i,0,n-1) a[i]=a[i]*Inv%P;
    }
}

V operator * (V a,V b){
    if(!a.size() || !b.size()) return { };
    int n=a.size()+b.size()-1,R=Init(n);
    a.resize(R),b.resize(R);
    NTT(R,a,1),NTT(R,b,1);
    rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
    NTT(R,a,-1);
    a.resize(n);
    return a;
}
V operator + (V a,V b){
    if(a.size()<b.size()) swap(a,b);
    rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
    return a;
}

V F[55],A,B;
int S,L[55];

int main(){
    Init();
    n=rd(),k=rd();
    rep(i,1,n) S+=L[i]=rd();
    sort(L+1,L+n+1);
    int InvS=qpow(S);
    F[0]={1};
    rep(i,1,n) {
        int W=(L[i]-1)/k;
        A.clear(),A.resize(W+1);
        B.clear(),B.resize(W+1);
        // 注意 L[i]==j*k && j==1 时会出现side condition
        // 也就是 L=k=1 的情况
        rep(j,0,W) {
            int w=1ll*(L[i]-j*k)*InvS%P;
            A[j]=1ll*(j&1?P-I[j]:I[j])*qpow(w,j)%P;
            if(j) B[j]=1ll*(j&1?P-I[j]:I[j])*qpow(w,j-1)%P*j%P;
        }
        drep(j,i,0) {
            if(!j) F[j]=F[j]*A;
            else F[j]=F[j]*A+F[j-1]*B;
        }
    }
    // 就硬乘。。
    // 如果分治合并每个，复杂度变为log n
    int ans=0;
    rep(i,0,n) {
        rep(j,max(i,1),F[i].size()-1) if(F[i][j]) {
            int k=j-i;
            ans=(ans+1ll*F[i][j]*J[k]%P*qpow(1ll*j*::k*InvS%P,P-1-k-1))%P;
        }
    }
    ans=(P-ans)%P;
    printf("%d\n",ans);
}