P5824 十二重计数法

十二重计数法 ×

刻刻帝 十二种子弹 √

以下复杂度均在已经预处理完逆元、阶乘逆元和阶乘的情况下计算。

咋一股 这玩意的味道。。。不过简单多了

  1. 球之间互不相同，盒子之间互不相同。

显然是 (m^n)​​​。复杂度 (O(log n))​。

ll Aleph(){return qpow(m,n);}
  1. 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。

一个一个放，所以是 (m^underline n)​​。复杂度 (O(n))​。

ll Bet(){
	ll ret=1;
	rep(i,m-n+1,m)ret=ret*i%P;
	return ret;
}
  1. 球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

对 1 考虑做容斥，所以答案是

[sum_{i=0}^m(-1)^iinom{m}{i}(m-i)^n ]

复杂度 (O(mlog n))​​。

另外你也可以考虑用斯特林数，答案就是 (egin{Bmatrix}n\mend{Bmatrix} imes m!)​​，这里采用的是前面的做法。

ll Gimel(){
	ll ret=0;
	rep(i,0,m)
		if(i&1)ret=(ret-C(m,i)*qpow(m-i,n)%P+P)%P;
		else ret=(ret+C(m,i)*qpow(m-i,n)%P)%P;
	return ret;
}
  1. 球之间互不相同，盒子全部相同。

枚举非空盒子个数，所以是

[sum_{i=1}^{m}egin{Bmatrix}n\mend{Bmatrix} ]

来一发 第二类斯特林数·行，求个前缀和即可。复杂度 (O(nlog n)-O(1))​​​​​（固定 (n)）。

void Zaphkiel(){
	vec f(n+1),g(n+1);
	rep(i,0,n){
		f[i]=1ll*qpow(i,n)*invfac[i]%P;
		g[i]=invfac[i];
		if(i&1)g[i]=P-g[i];
	}
	S=mul(f,g,n<<1);
	S.resize(n+1);
}
ll Dalet(){
	ll ret=0;
	rep(i,1,min(m,n))ret=(ret+S[i])%P;
	return ret;
}

同时第三题的代码也可以简化为：

ll Gimel(){return 1ll*(m>n?0:S[m])*fac[m]%P;}
  1. 球之间互不相同，盒子全部相同，每个盒子至多装一个球。

显然是 ([nle m])​​。复杂度 (O(1))​​。

ll He(){return (n<=m);}
  1. 球之间互不相同，盒子全部相同，每个盒子至少装一个球。

显然是 (egin{Bmatrix}n\mend{Bmatrix})​​​​​，可以使用通项（不过也可以用 4 中算的整），复杂度 (O(nlog m)/O(nlog n)-O(1))​​​​（固定 (n)）。

ll Vav(){return S[m];}
  1. 球全部相同，盒子之间互不相同。

小学奥数插板法可知为 (dbinom{n+m-1}{m-1})​​，复杂度 (O(1))​。

ll Zayin(){return C(n+m-1,m-1);}
  1. 球全部相同，盒子之间互不相同，每个盒子至多装一个球。

显然是 (dbinom{m}{n})​，复杂度 (O(1))​。

ll Het(){return C(m,n);}
  1. 球全部相同，盒子之间互不相同，每个盒子至少装一个球。

小学奥数插板法可知为 (dbinom{n-1}{m-1})​，复杂度 (O(1))​​。

ll Tet(){return C(n-1,m-1);}
  1. 球全部相同，盒子全部相同。

本题唯一有点意思的东西。所以另外十一题放这干啥，搁这十二合一恶心人呢

考虑一个经典的 dp：(f_{i,j}) 表示 (i) 个球，(j)​​ 个盒子。那么容易得到

[f_{i,j}=f_{i,j-1}+f_{i-j,j} ]

那么考虑设 (F_j(x)) 为 ({f_{i,j}}_{i=0}^{infty}) 的 OGF，可得：

[egin{aligned} [x^i]F_j(x)&=[x^i]F_{j-1}(x)+[x^{i-j}]F_j(x)\ F_j(x)&=F_{j-1}(x)+x^jF_j(x)\ F_j(x)&=F_{j-1}(x)frac{1}{1-x^j}\ F_j(x)&=prod_{i=1}^{j}frac{1}{1-x^j}\ ln F_k(x)&=-sum_{i=1}^kln(1-x^i)\ ln F_k(x)&=-sum_{i=1}^ksum_{j=1}^{infty}frac{x^{ij}}{j} end{aligned} ]

暴力计算出 (ln F_m(x))​​​ 对其求 exp 即可，复杂度 (O(nlog n)-O(1))​​​（固定 (m)）。

void Zaphkiel(){
    ...
	rep(i,0,n)f[i]=0;
	rep(i,1,m)for(ll j=1;i*j<=n;j++)f[i*j]=(f[i*j]+inv[j])%P;
	getexp(f,F,n+1);
}
ll Yod(){return F[n];}
  1. 球全部相同，盒子全部相同，每个盒子至多装一个球。

显然是 ([nle m])。复杂度 (O(1))。

ll Yod_Alef(){return (n<=m);}
  1. 球全部相同，盒子全部相同，每个盒子至少装一个球。

每个盒子扔掉一个球就变成了 10。复杂度 (O(nlog n)-O(1))（固定 (m)​）。

ll Yod_Bet(){return n<m?0:F[n-m];}

最后缝合一下就是完整代码了，如下：

// Problem: P5824 十二重计数法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5824
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '
' 
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
inline void chkmax(ll &x,ll y){if(x<y)x=y;}
inline void chkmin(ll &x,ll y){if(x>y)x=y;}
struct IO_Tp {
    const static int _I_Buffer_Size = 2 << 22;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;

    const static int _O_Buffer_Size = 2 << 22;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(ll &res) {
        ll f=1;
        while (!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        return *this;
    }

    IO_Tp &operator<<(ll n) {
        if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch) {
        *_O_pos++ = ch;
        return *this;
    }
} IO;
ll n,m;
typedef vector<int> vec;
const int N=4194304,P=998244353;
int inv[N],fac[N],invfac[N],pw[N];
namespace Poly{
    const int G=3,img=86583718;
    int lmt,rev[N];
    inline int qpow(int a,int k){
        int ret=1;
        while(k){
            if(k&1)ret=1LL*ret*a%P;
            a=1LL*a*a%P;
            k>>=1;
        }
        return ret%P;
    }
    inline void init(int n){
        lmt=1;int t=0;
        while(lmt<n)lmt<<=1,t++;
        for(int i=1;i<lmt;i++)rev[i]=(rev[i>>1]>>1)|(i&1)<<(t-1);
    }
    inline void NTT(vec&A,int lmt,int tp){
        if(A.size()<lmt)A.resize(lmt);
        for(int i=0;i<lmt;i++)if(i<rev[i])swap(A[i],A[rev[i]]);
        for(int m=1,t=0;m<lmt;m<<=1,t++)
            for(int j=0,Wn=pw[t+1];j<lmt;j+=m<<1)
                for(int k=0,w=1,x,y;k<m;k++,w=1LL*w*Wn%P)
                    x=A[j+k],y=1LL*w*A[j+k+m]%P,A[j+k]=(x+y)%P,A[j+k+m]=(x-y+P)%P;
        if(tp==1)return;
        reverse(A.begin()+1,A.begin()+lmt);
        for(int i=0,inv=qpow(lmt,P-2);i<lmt;i++)A[i]=1LL*A[i]*inv%P;
    } 
    vec mul(vec f,vec g,int len){
        init(len);
        f.resize(lmt),g.resize(lmt);
        NTT(f,lmt,1);NTT(g,lmt,1);
        for(int i=0;i<lmt;i++)f[i]=1LL*f[i]*g[i]%P;
        NTT(f,lmt,-1);
        return f;
    } 
    void getinv(vec&f,vec&g,int len){
        if(f.size()<(len<<2))f.resize(len<<2);
        if(g.size()<(len<<2))g.resize(len<<2);
        if(len==1){g[0]=qpow(f[0],P-2);return;}
        getinv(f,g,len+1>>1);
        init(len<<1);
        vec c(lmt);
        copy(f.begin(),f.begin()+len,c.begin());
        NTT(c,lmt,1),NTT(g,lmt,1);
        for(int i=0;i<lmt;i++)g[i]=1LL*(2LL-1LL*g[i]*c[i]%P+P)%P*g[i]%P;
        NTT(g,lmt,-1);
        for(int i=len;i<lmt;i++)g[i]=0;
    }
    vec getdev(vec f,int len){
        vec g(len-1);
        for(int i=1;i<len;i++)g[i-1]=1LL*i*f[i]%P;
        return g;
    }
    vec getinvdev(vec f,int len){
        vec g(len+1);
        for(int i=1;i<len;i++)g[i]=1LL*f[i-1]*inv[i]%P;
        return g;
    }
    vec getln(vec f,int len){
        vec a=getdev(f,len),b;
        getinv(f,b,len);
        return getinvdev(mul(a,b,len<<1),len);
    }
    void getexp(vec f,vec&g,int len){
        if(g.size()<(len<<2))g.resize(len<<2);
        if(len==1){g[0]=1;return;}
        getexp(f,g,len+1>>1);
        init(len<<1);
        vec d=getln(g,len),e(f.begin(),f.begin()+len);
        NTT(g,lmt,1),NTT(d,lmt,1),NTT(e,lmt,1);
        for(int i=0;i<lmt;i++)g[i]=1LL*(1-d[i]+e[i]+P)*g[i]%P;
        NTT(g,lmt,-1);
        for(int i=len;i<lmt;i++)g[i]=0;
    }
    vec getpow(vec f,int len,int k){
        vec g(len),h=getln(f,len);
        for(int i=0;i<len;i++)h[i]=1LL*h[i]*k%P;
        getexp(h,g,len);
        return g;
    }
}
using namespace Poly;
vec S,F;
int Kurumi(int n){
    int lmt=1;
    inv[0]=inv[1]=1;
    while(lmt<n)lmt<<=1;
    for(int i=2;i<lmt;i++)inv[i]=1LL*(P-P/i)*inv[P%i]%P;
    fac[0]=invfac[0]=1;
    for(int i=1;i<lmt;i++)fac[i]=1LL*fac[i-1]*i%P,invfac[i]=1LL*invfac[i-1]*inv[i]%P;
    pw[23]=Poly::qpow(Poly::G,119);
    for(int i=22;i>=0;i--)pw[i]=1LL*pw[i+1]*pw[i+1]%P;
    return lmt;
}
ll C(ll n,ll m){return 1ll*fac[n]*invfac[m]%P*invfac[n-m]%P;}
void Zaphkiel(){
    vec f(n+1),g(n+1);
    rep(i,0,n){
        f[i]=1ll*qpow(i,n)*invfac[i]%P;
        g[i]=invfac[i];
        if(i&1)g[i]=P-g[i];
    }
    S=mul(f,g,n<<1);
    S.resize(n+1);
    rep(i,0,n)f[i]=0;
    rep(i,1,m)for(ll j=1;i*j<=n;j++)f[i*j]=(f[i*j]+inv[j])%P;
    getexp(f,F,n+1);
}
ll Aleph(){return qpow(m,n);}
ll Bet(){
    ll ret=1;
    rep(i,m-n+1,m)ret=ret*i%P;
    return ret;
}
ll Gimel(){return 1ll*(m>n?0:S[m])*fac[m]%P;}
ll Dalet(){
    ll ret=0;
    rep(i,1,min(m,n))ret=(ret+S[i])%P;
    return ret;
}
ll He(){return (n<=m);}
ll Vav(){return m>n?0:S[m];}
ll Zayin(){return C(n+m-1,m-1);}
ll Het(){return C(m,n);}
ll Tet(){return C(n-1,m-1);}
ll Yod(){return F[n];}
ll Yod_Alef(){return (n<=m);}
ll Yod_Bet(){return n<m?0:F[n-m];}
int main(){
    IO>>n>>m;
    Kurumi(n<<2);
    Zaphkiel();
    IO<<Aleph()<<endl;
    IO<<Bet()<<endl;
    IO<<Gimel()<<endl;
    IO<<Dalet()<<endl;
    IO<<He()<<endl;
    IO<<Vav()<<endl;
    IO<<Zayin()<<endl;
    IO<<Het()<<endl;
    IO<<Tet()<<endl;
    IO<<Yod()<<endl;
    IO<<Yod_Alef()<<endl;
    IO<<Yod_Bet()<<endl;
    return 0;
}

最后，简单讲一下这题和 more transformations of integer sequences 的关系（不知道的人可以看下 rqy 课件，或者这里也可以）：

  1. (operatorname{AIJ}_m(a))​，其中​​ (a_x=1,forall x)​。​​​
  2. (operatorname{AIJ}_m(a))，其中​ (a_1=1,a_x=0,x>1)​。​
  3. (operatorname{AIJ}_m(a))​，其中 (a_1=0,a_x=1,x>1)​​。
  4. (operatorname{AIK}_m(a))​，其中 (a_x=1,forall x)​​。
  5. (operatorname{AIK}_m(a))，其中 (a_1=1,a_x=0,x>1)​。
  6. (operatorname{AIK}_m(a))，其中 (a_x=0,a_x=1,x>1)​。
  7. (operatorname{EIJ}_m(a))​，其中 (a_x=1,forall x)​​。
  8. (operatorname{EIJ}_m(a))，其中 (a_1=1,a_x=0,x>1)。
  9. (operatorname{EIJ}_m(a))，其中 (a_x=0,a_x=1,x>1)。
  10. (operatorname{EIK}_m(a))，其中 (a_x=1,forall x)。
  11. (operatorname{EIK}_m(a))，其中 (a_1=1,a_x=0,x>1)。
  12. (operatorname{EIK}_m(a))，其中 (a_x=0,a_x=1,x>1)。

如以上有问题请指出，谢谢。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/happydef/p/Tokisaki-Kurumi.html