CF Round#698 Div1. Nezzar and Chocolate Bars

Posted on Edited on In

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}n![x^n](x^k e^{cx})=\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);
}