[数学记录]P5162 WD与积木
command_block
2019-12-30 13:08:09
**题意** : 把$1...n$分割成若干个集合,集合之间**有顺序**,问所有不同的分割方法之中,集合个数的期望。
先考虑一个弱化版的问题 : 统计分割方法数。
~~观察数据可得~~这题是个多项式重工业,考虑使用EGF。
容易得到单个集合的EGF为 : $F(x)=\{0,1,1,1...\}=\sum\limits_{i=1}\dfrac{x^i}{i!}=e^x-1$
注意,把这东西是不能直接EXP的。
EXP的生成函数意义 : $\exp F(x)=\sum\limits_{i=0}\dfrac{F(x)^i}{i!}$,即无序组合背包。
这里是有序排列背包,这里有一个入门级经典结论 :
$\sum\limits_{i=0}F(x)^i=\dfrac{1}{1-F(x)}$ , 这个东西就是有序排列背包。
那么背出来就是$\dfrac{1}{2-e^x}$。
接下来考虑求集合个数总和,看起来不太好直接搞。
我们怎么统计集合呢?每卷一次$F(x)$就算多了一个集合,我们前面的有序排列背包枚举了$F(x)$的指数,直接借过来用就好了。
得到这个式子 : $\sum\limits_{i=0}iF(x)^i$
无穷级数,考虑扰动法 : $(1-x)\sum\limits_{i=0}ix^i=\sum\limits_{i=0}ix^i-\sum\limits_{i=1}(i-1)x^i=\sum\limits_{i=1}x^i=\dfrac{x}{1-x}$
得到$\sum\limits_{i=0}iF(x)^i=\dfrac{F(x)}{(1-F(x))^2}=\dfrac{e^x-1}{(2-e^x)^2}$
会乘法+求逆就可以做了,注意得到的是EGF,记得还原。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 998244353
#define G 3
#define Maxn 135000
using namespace std;
inline int read()
{
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
ll powM(ll a,ll t=mod-2)
{
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int tr[Maxn<<1];
ll invG=powM(G);
void NTT(ll *f,short op,int n)
{
for (int i=0;i<n;i++)
if (i<tr[i])swap(f[i],f[tr[i]]);
for(int p=2;p<=n;p<<=1){
int len=p/2;
ll tG=powM(op==1 ? G:invG,(mod-1)/p);
for(int k=0;k<n;k+=p){
ll buf=1;
for(int l=k;l<k+len;l++){
int tt=buf*f[len+l]%mod;
f[len+l]=f[l]-tt;
if (f[len+l]<0)f[len+l]+=mod;
f[l]+=tt;
if (f[l]>=mod)f[l]-=mod;
buf=buf*tG%mod;
}
}
}
}
ll _g1[Maxn<<1];
void times(ll *f,ll *g,int len,int lim)
{
int m=len+len,n;
for(int i=0;i<len;i++)_g1[i]=g[i];
#define g _g1
for(n=1;n<m;n<<=1);
for(int i=len;i<n;i++)g[i]=0;
ll invn=powM(n);
for(int i=0;i<n;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,1,n);NTT(g,1,n);
for(int i=0;i<n;++i)f[i]=f[i]*g[i]%mod;
NTT(f,-1,n);
for(int i=0;i<lim;++i)
f[i]=f[i]*invn%mod;
for(int i=lim;i<n;++i)f[i]=0;
#undef g
}
ll _w2[Maxn<<1],_r2[Maxn<<1];
void invp(ll *f,int m)
{
int n;for (n=1;n<m;n<<=1);
#define w _w2
#define r _r2
w[0]=powM(f[0]);
for (int len=2;len<=n;len<<=1){
for (int i=0;i<(len>>1);i++)
r[i]=(w[i]<<1)%mod;
times(w,w,len>>1,len);
times(w,f,len,len);
for (int i=0;i<len;i++)
w[i]=(r[i]-w[i]+mod)%mod;
}for (int i=0;i<m;i++)f[i]=w[i];
for (int i=0;i<n;i++)w[i]=r[i]=0;
#undef w
#undef r
}
ll fac[Maxn],inv[Maxn];
void Init(int lim)
{
fac[0]=1;
for (int i=1;i<=lim;i++)
fac[i]=fac[i-1]*i%mod;
inv[lim]=powM(fac[lim])%mod;
for (int i=lim;i;i--)
inv[i-1]=inv[i]*i%mod;
}
int T,n,m[Maxn];
ll F[Maxn<<1],S[Maxn<<1],sav[Maxn];
int main()
{
scanf("%d",&T);
for (int i=1;i<=T;i++)
n=max(n,(m[i]=read()));
n++;Init(n);
F[0]=1;
for (int i=1;i<n;i++)
F[i]=mod-(S[i]=inv[i]);
invp(F,n);
for (int i=1;i<=T;i++)
sav[i]=F[m[i]]*fac[m[i]]%mod;
times(F,F,n,n);
times(F,S,n,n);
for (int i=1;i<=T;i++)
printf("%lld\n",powM(sav[i])*F[m[i]]%mod*fac[m[i]]%mod);
return 0;
}
```