[数学记录]P5824 十二重计数法
command_block
2019-12-27 23:34:25
重工业题来咯!
兔队的人话题意：
有 $n$ 个小球，$m$ 个盒子, 每个小球应该恰好扔进一个盒子。
**十二重计数** :
每两个小球之间都是可以区分的或不可以区分的（2）
每两个盒子之间都是可以区分的或不可以区分的（2）
对盒子内的球数无要求或每个盒子内最多装一个球或不允许空盒子（3）
$2 \times 2 \times 3 = 12$
**前置芝士** : [斯特林数小结](https://www.luogu.com.cn/blog/command-block/si-te-lin-shuo-zong-jie)
[题解 P4389 【付公主的背包】](https://www.luogu.com.cn/blog/command-block/solution-p4389)
- $\large\text{I}$ 小球可区分,盒子可区分,球量无要求。 $m^n$.
- $\large\text{II}$ 小球可区分,盒子可区分,球量至多一个。 $m^{\underline{n}}$
- $\large\text{III}$ 小球可区分,盒子可区分,球量至少一个。 $m!\begin{Bmatrix}n\\m\end{Bmatrix}$
- $\large\text{IV}$ 小球可区分,盒子不区分,球量无要求。
考虑枚举占用的盒子个数,就得到第$m$行第二类斯特林数的和。
- $\large\text{V}$ 小球可区分,盒子不区分,球量至多一个。
$[n\leq m]$ (可以得到装得下的都是同一种方案)
- $\large\text{VI}$ 小球可区分,盒子不区分,球量至少一个。
就是第二类斯特林数的定义 : $\begin{Bmatrix}n\\m\end{Bmatrix}$
- $\large\text{VII}$ 小球不区分,盒子可区分,球量无要求。
其实就等价于$(n+1)\times m$的方格,只能右下走,斜向跨越的方案数。
向下走等同于放球,向右走等同于去往下一个盒子。
总的来说就是$n+m-1$步里面选$n$步向下,即$\dbinom{n+m-1}{n}$。
- $\large\text{VIII}$ 小球不区分,盒子可区分,球量至多一个。 $\dbinom{m}{n}$
- $\large\text{IX}$ 小球不区分,盒子可区分,球量至少一个。
插板法 : 一列$n$个球分成$m-1$段,每段都不能为空,即$\dbinom{n-1}{m-1}$
- $\large\text{X}$ 小球不区分,盒子不区分,球量无要求。
这就是个整数拆分问题 : 把$n$分成$m$个无序整数的方案数。
由于这个拆分是无序的,我们按照从大到小的顺序摆放成一个图,第$i$行表示第$i$次分出的个数,要求个数不增。
```
13=6+4+2+1
******
****
**
*
```
把这个图翻转,显然是一一对应。
```
13=4+3+2+2+1+1
****
***
**
**
*
*
```
这也得到一个结论 : 把$n$分成$m$个无序整数的方案数 = 把$n$分成用$m$以内的**正**整数分拆的方案数。
后者比较容易计算 : 用$k$来分拆的OGF是$\{1,x^k,x^{2k}...\}=\dfrac{1}{1-x^k}$
总的来说就是$p(n,m)=[x^n]\prod\limits_{i=1}^m\left(\dfrac{1}{1-x^i}\right)$
剩下的就是P4389了。
- $\large\text{XI}$ 小球不区分,盒子不区分,球量至多一个。
$[n\leq m]$ (可以得到装得下的都是同一种方案)
- $\large\text{XII}$ 小球不区分,盒子不区分,球量至少一个。
先给每个盒子放一个,然后变成了$X$,即$p(n-m,m)$
```cpp
#include<algorithm>
#include<cstdio>
#include<ctime>
#define ll long long
#define mod 998244353
#define G 3
#define Maxn 270000
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;
}
inline void print(ll *f,int len)
{
for (int i=0;i<len;i++)
printf("%lld ",f[i]);
puts("");
}
ll powM(ll a,ll t=mod-2)
{
ll ans=1,buf=a;
while(t){
if(t&1)ans=(ans*buf)%mod;
buf=(buf*buf)%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>>1,
tG=powM(op==1 ? G:invG,(mod-1)/p);
for (int k=0;k<n;k+=p){
ll buf=1;
for (int i=k;i<k+len;i++){
int sav=f[len+i]*buf%mod;
f[len+i]=(f[i]-sav+mod)%mod;
f[i]=(f[i]+sav)%mod;
buf=buf*tG%mod;
}
}
}
}
ll _g1[Maxn<<1];
void times(ll *f,ll *g,int len1,int len2,int lim)
{
int m=len1+len2-1,n;
for(int i=0;i<len2;i++)_g1[i]=g[i];
#define g _g1
for(n=1;n<m;n<<=1);
for(int i=len2;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>>1,len);
times(w,f,len,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
}
void dao(ll *f,int m)
{
for (int i=1;i<m;i++)
f[i-1]=f[i]*i%mod;
f[m-1]=0;
}
void jifen(ll *f,int m)
{
for (int i=m;i;i--)
f[i]=f[i-1]*powM(i)%mod;
f[0]=0;
}
ll _s3[Maxn<<2];
void lnp(ll *f,int m)
{
ll *sav=_s3;
for (int i=0;i<m;i++)sav[i]=f[i];
invp(sav,m);dao(f,m);
times(f,sav,m-1,m,m);
jifen(f,m-1);
for (int i=0;i<m;i++)sav[i]=0;
}
ll _xp[Maxn<<2],_xp2[Maxn<<2];
void exp(ll *f,int m)
{
ll *s=_xp,*s2=_xp2;
int n=1;for(;n<m;n<<=1);
s2[0]=1;
for (int len=2;len<=n;len<<=1){
for (int i=0;i<(len>>1);i++)s[i]=s2[i];
lnp(s,len);
for (int i=0;i<len;i++)
s[i]=(f[i]-s[i]+mod)%mod;
s[0]=(s[0]+1)%mod;
times(s2,s,len>>1,len,len);
}for (int i=0;i<m;i++)f[i]=s2[i];
for (int i=0;i<n;i++)s[i]=s2[i]=0;
}
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]);
for (int i=lim;i;i--)
inv[i-1]=inv[i]*i%mod;
}
ll ans[14];
int n,m;
void solve1()
{
ll buf;
ans[1]=powM(m,n);
if (n<=m){
ans[2]=ans[5]=ans[11]=1;
for (int i=m-n+1;i<=m;i++)
ans[2]=ans[2]*i%mod;
ans[8]=fac[m]*inv[n]%mod*inv[m-n]%mod;
}
ans[7]=1;
for (int i=m;i<=n+m-1;i++)
ans[7]=ans[7]*i%mod;
ans[7]=ans[7]*inv[n]%mod;
if (n>=m)
ans[9]=fac[n-1]*inv[m-1]%mod*inv[n-m]%mod;
}
ll f[Maxn<<1],g[Maxn<<1];
void solve2()
{
for (int i=0;i<=min(n,m);i++){
f[i]=powM(i,n)*inv[i]%mod;
g[i]=(i&1) ? mod-inv[i] : inv[i];
}times(f,g,min(n,m)+1,min(n,m)+1,min(n,m)+1);
ans[3]=fac[m]*f[m]%mod;
for (int i=1;i<=min(n,m);i++)ans[4]+=f[i];
ans[4]%=mod;
ans[6]=n<m ? 0 : f[m];
for (int i=0;i<=m;i++)f[i]=0;
}
void solve3()
{
for (int i=1;i<=m;i++)
for (int j=0;j<=n;j+=i)
f[j]=(f[j]+inv[j/i]*fac[j/i-1])%mod;
exp(f,n+1);
ans[10]=f[n];
if (n>=m)ans[12]=f[n-m];
}
int main()
{
n=read();m=read();Init(max(n,m));
solve1();solve2();solve3();
for (int i=1;i<=12;i++)
printf("%lld\n",ans[i]);
return 0;
}
```