P5824 十二重计数法
Petit_Souris
·
·
个人记录
感觉不难，速通了。
I
[\frac{x^n}{n!}](\text{e}^x)^m=m^n
一个盒子的 EGF 是 \text{e}^x，拆分到 m 个盒子即 (\text{e}^x)^m。
II
[\frac{x^n}{n!}](1+x)^m=\binom{m}{n}n!
一个盒子的 EGF 是 \frac{x^0}{0!}+\frac{x^1}{1!}。
- 组合意义：依次放入 n 个球，第 i 个球有 \max(0,m-i+1) 种方法，即 m^{\underline{n}}=\binom{m}{n}n!。
III
[\frac{x^n}{n!}](\text{e}^x-1)^m=[\frac{x^n}{n!}]\sum\limits_{i=0}^m\binom{m}{i}(-1)^{m-i}(\text{e}^x)^i=\sum\limits_{i=0}^m\binom{m}{i}(-1)^{m-i}i^n
一个盒子的 EGF \text{e}^x-1 表示任意放 减去 一个不放。
- 组合意义：考虑容斥，枚举选择了 i 个空盒子，剩下的球任意分配到 m-i 个盒子中。
IV
空盒子需要互相区分，而有球的盒子已经被球区分了，枚举有球的盒子数量。
[\frac{x^n}{n!}]\sum\limits_{i=0}^{m}\frac{1}{i!}(\text{e}^x-1)^i=[\frac{x^n}{n!}]\sum\limits_{i=0}^m\frac{1}{i!}\sum\limits_{j=0}^{i}\binom{i}{j}(-1)^{i-j}(\text{e}^{x})^j
=\sum\limits_{i=0}^{m}\frac{1}{i!}\sum\limits_{j=0}^{i}\binom{i}{j}(-1)^{i-j}j^n=\sum\limits_{i=0}^{m}\sum\limits_{j=0}^{i}\frac{1}{(i-j)!j!}(-1)^{i-j}j^n
转为枚举 k=i-j，那么 k=0,1,\dots m-j。
=\sum\limits_{j=0}^{m}\frac{j^n}{j!}\sum\limits_{k=0}^{m-j}\frac{(-1)^k}{k!}
现在关于 j,k 独立了，直接预处理后半部分即可。
这就是第二类斯特林数 S_{n,i} 的行和，实际上我们是在容斥有多少个空盒子。
所以其实也可以算一行 S 来做？
V
[\frac{x^n}{n!}]\sum\limits_{i=0}^{m}\frac{1}{i!}x^i=[n\le m]
- 组合意义：放进去之后所有状态都是相同的，只需要判断是否有解（乐得不行）。
VI
[\frac{x^n}{n!}]\frac{1}{m!}(\text{e}^x-1)^m=\frac{1}{m!}\sum\limits_{i=0}^{m}\binom{m}{i}(-1)^{m-i}i^n
VII
[x^n](1+x+x^2+\dots )^m=[x^n]\frac{1}{(1-x)^m}=\binom{n+m-1}{m-1}
- 组合意义：插板法，补上 m-1 个后相当于放 m-1 块隔板，分成的 n 部分都非空。
VIII
[x^n](1+x)^m=\binom{m}{n}
IX
[x^n](x(1+x+x^2+\dots))^m=[x^{n-m}](1+x+x^2+\dots )^m=\binom{n-1}{m-1}
X
[x^n]\prod\limits_{i=1}^{m}\frac{1}{1-x^i}
施 ln - exp trick，即可在 \mathcal O(n\log n) 时间内解决。
XI
同 V。
XII
代码：
```cpp
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const ll N=2e6+9;
const ll Mod=998244353,G=3,invG=332748118,inv2=(Mod+1)>>1;
ll fac[N],ifac[N],inv[N];
ll pw(ll x,ll p){
ll res=1;
while(p){
if(p&1)res=res*x%Mod;
x=x*x%Mod;
p>>=1;
}
return res;
}
void Init(ll n){
fac[0]=1;
rep(i,1,n)fac[i]=fac[i-1]*i%Mod;
ifac[n]=pw(fac[n],Mod-2);
per(i,n-1,0)ifac[i]=ifac[i+1]*(i+1)%Mod;
rep(i,1,n)inv[i]=ifac[i]*fac[i-1]%Mod;
}
ll C(ll x,ll y){
if(x<y||y<0)return 0;
return fac[x]*ifac[y]%Mod*ifac[x-y]%Mod;
}
namespace Poly{
struct poly{
vector<int>a;
int size()const{return a.size();}
void resize(int n){a.resize(n);}
int operator[](int n)const{
if((int)a.size()<=n)return 0;
return a[n];
}
int &operator[](int n){
if((int)a.size()<=n)a.resize(n+1);
return a[n];
}
};
int r[N],w[N];
int init(int n){
int p=1,c=0;
while(p<=n)p<<=1,c++;
r[0]=0;
rep(i,1,p-1)r[i]=(r[i>>1]>>1)|((i&1)<<(c-1));
return p;
}
void NTT(poly&a,int n,int sgn){
rep(i,0,n-1){
if(i<r[i])swap(a[i],a[r[i]]);
}
for(int mid=1;mid<n;mid<<=1){
int wn=pw(sgn==1?G:invG,(Mod-1)/(mid<<1)),R=(mid<<1);
for(int j=0;j<n;j+=R){
int w=1;
rep(k,0,mid-1){
int x=a[j+k],y=1ll*a[j+k+mid]*w%Mod;
a[j+k]=(x+y)%Mod;
a[j+k+mid]=(x-y+Mod)%Mod;
w=1ll*w*wn%Mod;
}
}
}
if(~sgn)return ;
ll inv=pw(n,Mod-2);
rep(i,0,n-1)a[i]=1ll*a[i]*inv%Mod;
}
poly operator+(const poly&a,const poly&b){
poly c;c.resize(max(a.size(),b.size()));
rep(i,0,max((ll)a.size()-1,(ll)b.size()-1))c[i]=(a[i]+b[i])%Mod;
return c;
}
poly operator*(const poly&a,const int&b){
poly c;
c.resize(a.size());
rep(i,0,(int)a.size()-1)c[i]=1ll*a[i]*b%Mod;
return c;
}
poly operator*(const poly&a,const poly&b){
int p=init(a.size()+b.size());
poly tmp1=a,tmp2=b;
tmp1.resize(p),tmp2.resize(p);
NTT(tmp1,p,1);
NTT(tmp2,p,1);
rep(i,0,p-1)tmp1[i]=1ll*tmp1[i]*tmp2[i]%Mod;
NTT(tmp1,p,-1);
tmp1.resize(a.size()+b.size());
return tmp1;
}
poly Inv(int n,const poly&a){
poly b;
if(n==1){
b.resize(1);
b[0]=pw(a[0],Mod-2);
return b;
}
b=Inv((n+1)/2,a);
int p=init(n*2);
b.resize(p);
poly tmp1;tmp1.resize(p);
rep(i,0,n-1)tmp1[i]=a[i];
rep(i,n,p-1)tmp1[i]=0;
NTT(tmp1,p,1),NTT(b,p,1);
rep(i,0,p-1)b[i]=1ll*(2-1ll*tmp1[i]*b[i]%Mod+Mod)*b[i]%Mod;
NTT(b,p,-1);
b.resize(n);
return b;
}
poly Sqrt(int n,const poly&a){
poly b;
if(n==1){
b.resize(1);
b[0]=1;
return b;
}
b=Sqrt((n+1)/2,a);
int p=init(n*2);
b.resize(p);
poly tmp1=Inv(n,b);
poly tmp2;
tmp1.resize(p),tmp2.resize(p);
rep(i,0,n-1)tmp2[i]=a[i];
rep(i,n,p-1)tmp2[i]=0;
NTT(tmp2,p,1),NTT(b,p,1),NTT(tmp1,p,1);
rep(i,0,p-1)b[i]=1ll*(b[i]+1ll*tmp1[i]*tmp2[i])%Mod*inv2%Mod;
NTT(b,p,-1);
b.resize(n);
return b;
}
poly Derivative(int n,const poly&a){
poly b;
b.resize(n);
rep(i,1,n-1)b[i-1]=1ll*i*a[i]%Mod;
b[n-1]=0;
return b;
}
poly Intergral(int n,const poly&a){
poly b;
b.resize(n);
rep(i,1,n-1)b[i]=1ll*inv[i]*a[i-1]%Mod;
b[0]=0;
return b;
}
poly Ln(int n,const poly&a){
poly c=Derivative(n,a);
poly d=Inv(n,a);
c=c*d;
c.resize(n);
c=Intergral(n,c);
return c;
}
poly Exp(int n,const poly&a){
poly b;
if(n==1){
b.resize(1);
b[0]=1;
return b;
}
b=Exp((n+1)/2,a);
b.resize(n);
poly tmp1=Ln(n,b);
int p=init(n*2);
b.resize(p),tmp1.resize(p);
rep(i,0,n-1)tmp1[i]=((a[i]-tmp1[i]+(!i))%Mod+Mod)%Mod;
rep(i,n,p-1)b[i]=tmp1[i]=0;
NTT(tmp1,p,1),NTT(b,p,1);
rep(i,0,p-1)b[i]=1ll*b[i]*tmp1[i]%Mod;
NTT(b,p,-1);
b.resize(n);
return b;
}
poly Pow(int n,const poly&a,int k1,int k2){
//k mod P = k1, k mod phi(P) = k2
poly t=a;
ll rsh=0;
for(int i=0;i<n&&!t[i];++i)rsh++;
poly b;
if(rsh*k1>n)return b;
int u=pw(t[rsh],Mod-2),v=pw(t[rsh],k2);
rep(i,0,n-1)t[i]=1ll*t[i+rsh]*u%Mod;
t=Ln(n,t);
rep(i,1,n-1)t[i]=1ll*t[i]*k1%Mod;
t=Exp(n,t);
rsh*=k1;
rep(i,rsh,n-1)b[i]=1ll*t[i-rsh]*v%Mod;
return b;
}
}
using namespace Poly;
ll n,m;
namespace Q1{
void solve(){
write(pw(m,n)),putchar('\n');
}
}
namespace Q2{
void solve(){
write(C(m,n)*fac[n]%Mod),putchar('\n');
}
}
namespace Q3{
void solve(){
ll ans=0;
rep(i,0,m){
ll coef=((m-i)&1?Mod-1:1)*C(m,i)%Mod*pw(i,n)%Mod;
ans=(ans+coef)%Mod;
}
write(ans),putchar('\n');
}
}
namespace Q4{
ll pre[N];
void solve(){
pre[0]=1;
rep(i,1,m)pre[i]=(pre[i-1]+(i&1?Mod-1:1)*ifac[i])%Mod;
ll ans=0;
rep(i,0,m)ans=(ans+pw(i,n)*ifac[i]%Mod*pre[m-i])%Mod;
write(ans),putchar('\n');
}
}
namespace Q5{
void solve(){
write(n<=m),putchar('\n');
}
}
namespace Q6{
void solve(){
ll ans=0;
rep(i,0,m){
ll coef=((m-i)&1?Mod-1:1)*C(m,i)%Mod*pw(i,n)%Mod*ifac[m]%Mod;
ans=(ans+coef)%Mod;
}
write(ans),putchar('\n');
}
}
namespace Q7{
void solve(){
write(C(n+m-1,m-1)),putchar('\n');
}
}
namespace Q8{
void solve(){
write(C(m,n)),putchar('\n');
}
}
namespace Q9{
void solve(){
write(C(n-1,m-1)),putchar('\n');
}
}
namespace Q10{
poly f;
void solve(){
f.resize(n+1);
rep(i,1,m){
rep(j,1,n/i)f[i*j]=(f[i*j]+ifac[j]*fac[j-1])%Mod;
}
f=Exp(n+1,f);
write(f[n]),putchar('\n');
}
}
namespace Q11{
void solve(){
write(n<=m),putchar('\n');
}
}
namespace Q12{
void solve(){
if(n>=m)write(Q10::f[n-m]),putchar('\n');
else puts("0");
}
}
bool Med;
int main(){
cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
n=read(),m=read();
Init(4e5);
Q1::solve();
Q2::solve();
Q3::solve();
Q4::solve();
Q5::solve();
Q6::solve();
Q7::solve();
Q8::solve();
Q9::solve();
Q10::solve();
Q11::solve();
Q12::solve();
return 0;
}
```