P5748 集合划分计数题解（组合数学）

· · 题解

不需要多项式算法的通过方法

这道题原是一个多项式专业对口解决的题，然而看到多项式代码就头疼的蒟蒻也想通过。

第一阶段

其实我们可以用球盒模型相互转化解决这个问题。（如果你想一次了解各类 “球盒” 模型，可以看看 P5824 十二重计数法 这道题，它涵盖本文所有用到的模型）

首先，我们把这个问题化这样一个经典的模型：

将 n 个小球放入 n 个框子中的方案数。框子可以空，小球之间互不相同，框子之间互相相同。

它其实有个专门的名字叫做 bell 数。如何算它呢？我们发现，只要我们枚举装了球的框子的数量 m（对应本题中集合的数量），就可以把问题转化为一个新的模型，将 n 个小球放入 m 个框子中，每个框子都不可以空的方案数，小球之间互不相同，框子之间互相相同。设对于指定 n,m 上述问题的答案为 S_m^n，原问题的答案就是 \sum _{i=0}^m S_i^n。

发现 S 其实就是第二类斯特林数。如果不会可以看看这个题 P1655 小朋友的球 。但是出现了问题，如果用我们熟知的递推法求 S 可以通过 P1655，然而在这道题的数据范围下寄掉了。

所以我们需要继续转化，发现 S 的答案实际上是由 “将 n 个小球放入 m 个框子中，每个框子都不可以空，小球、框子之间都互不相同的方案数” 除以框子的排列方案数（即 m!）得到的。设对于指定 n,m 这个新的模型的答案为 f_m^n。

同样是枚举空框子个数 $i$，得出关系式 $$ g_m^n=\sum_{i=0}^m C_m^i f_{m-i}^n=\sum_{i=0}^m C_m^i f_i^n $$ 二项式反演得到 $$ f_m^n=\sum_{i=0}^m (-1)^{m-i}C_m^i g_i^n=\sum_{i=0}^m (-1)^{m-i}\frac{m!i^n}{i!(m-i)!} $$ ### 第二阶段 这时在 $n,m\le 10^5$ 的范围下，我们可以算指定 $f$ 的值，也可以算 $S$ 的值，可是原问题还有一个加和，那么就会 T。所以我们看看怎么化式子。因为 $n$ 是没有变过的，以下式子里二维数组的表示我们不带 $n$。 $$ \left.\begin{matrix} f_m=\sum_{i=0}^m (-1)^{m-i}\frac{m!i^n}{i!(m-i)!} \\S_m=f_m \cdot\frac{1}{m!} \\ans=\sum _{i=0}^m S_i \end{matrix}\right\} \Rightarrow ans= \sum _{i=0}^m \sum_{j=0}^i \frac{(-1)^{i-j}j^n}{j!(i-j)!} $$ 交换求和号 $$ ans= \sum _{j=0}^m \sum_{i=j}^m \frac{(-1)^{i-j}j^n}{j!(i-j)!} =\sum _{j=0}^m \frac{j^n}{j!}\sum_{i=j}^m \frac{(-1)^{i-j}}{(i-j)!} $$ 发现后面的和式每项取值只与 $i-j$ 有关，我们换元。 $$ ans=\sum _{j=0}^m \frac{j^n}{j!}\sum_{t=0}^{m-j} \frac{(-1)^t}{t!} $$ 这样就可以了，后面的和式预处理前缀和，算整个的时候只有枚举 $j$ 的复杂度。 ### 第三阶段 计算一下复杂度，发现是 $O(T\cdot n\log n)$ 的（$\log$ 来自快速幂），还是差点。所以我们要把快速幂的复杂度搞出去。 观察和式，用到快速幂的有分母的求逆元，还有分子的 $j^n$。分母逆元因为阶乘预处理了，它也就可以预处理。分子的 $j^n$ 由于是每次询问需要 $j=0\to m$ 所有的值，可以用线性筛筛出来。 就搞定了！当然常数一定要写小一点！ ```cpp //P5748 #include<bits/stdc++.h> #define endl '\n' #define debug cout<<" awa\n"; using ll=long long; using ull=unsigned long long; using ld=long double; using namespace std; const int mod=998244353; int read() { int x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x; } int n; const int N=1e5+10; int fac[N],invfac[N]; int pw(int a,int b) { int ret=1; while(b) { if(b&1)ret=1ll*ret*a%mod; a=1ll*a*a%mod; b>>=1; } return ret; } void init() { fac[0]=1; for(int i=1;i<=1e5;i++) fac[i]=1ll*fac[i-1]*i%mod; for(int i=0;i<=1e5;i++) invfac[i]=pw(fac[i],mod-2); } int b[N],s[N],pm[N],tot; bool c[N]; inline void solve(){ init(); for(int i=2;i<=1e5;i++) { if(!c[i])pm[++tot]=i; for(int j=1;j<=tot;j++) { if(1ll*i*pm[j]>1e5||pm[j]>i)break; c[i*pm[j]]=1; if(i%pm[j]==0)break; } } int t;t=read(); while(t--) { n=read(); s[0]=0,s[1]=1; for(int i=2;i<=n;i++) { if(!c[i])s[i]=pw(i,n); for(int j=1;j<=tot;j++) { if(1ll*i*pm[j]>n||pm[j]>i)break; s[i*pm[j]]=1ll*s[i]*s[pm[j]]%mod; if(i%pm[j]==0)break; } } int ans=0,sum=0; for(int i=n;i>=0;i--) { sum=(1ll*sum+(((n-i)&1)?-1:1)*invfac[n-i])%mod; ans=(ans+1ll*invfac[i]*s[i]%mod*sum)%mod; } printf("%d\n",ans>=0?ans:ans+mod); } } int main() { solve(); const int _=0; return ~~(0^_^0); } ```