题解：P5824 十二重计数法

· · 题解

为什么这道题题解区全是多项式做法呢，看我不用多项式。

用多项式的可以跳过了。

I

乘法定理，每个球有 m 种选法，共 n 个球，结果是 m^n。

II

就是选 m 个盒子放 m 个球,再选进行排列，结果是：

C_n^m\cdot m! =\frac{n!\cdot m!}{m!\cdot (n-m)!}=\frac{n!}{(n-m)!}

III

考虑容斥。

钦定 k 个盒子为空，则剩下的 (m-k) 个盒子有 C_m^{m-k}=C_m^k 种可能，任意放有 (m-k)^n 个可能。这样子枚举时会枚举到后面若干种可能性有重复，待定系数后不难发现系数为 (-1)^k。所以有：

\sum_{k=1}^n (-1)^k\cdot C_m^k\cdot (m-k)^n

IV

第二类斯特林数 S(n,k) 是 n 个两两不同的元素放入 k 个互不区分的非空子集的方案数。有：

S(n,k)=\sum_{i=0}^k \frac{(-1)^{k-i}\cdot i^n}{i!\cdot (k-i)!}

由于集合互不区分，结果就是：

\begin{aligned} &\sum_{k=0}^m S(n,k)\\ =&\sum_{k=0}^m \sum_{i=0}^k \frac{(-1)^{k-i}\cdot i^n}{i!\cdot (k-i)!}\\ =&\sum_{i=0}^m \frac{i^n}{i!}\sum_{k=i}^m \frac{(-1)^{k-i}}{(k-i)!}\\ =&\sum_{i=0}^m \frac{i^n}{i!}\sum_{j=0}^{m-i} \frac{(-1)^{j}}{(j)!} \end{aligned}

记 H_n=\sum_{j=0}^{n} \frac{(-1)^{j}}{(j)!}，预处理 H 就做完了。

V

[n\le m]

显然，自证不难。

VI

注意到是第二类斯特林数定义。

S(n,m)=\sum_{i=0}^m \frac{(-1)^{m-i}\cdot i^n}{i!\cdot (m-i)!}

VII

考虑插板法，由于可以非空，有 n+m-1 个空，分为 m 个，插 m-1 个板。

C_{n+m-1}^{m-1}

VIII

从 m 个盒子中选 n 个装球。就是：

C_m^n

IX

球无序，所以先一个盒子放一个，剩下 n-m 个就是第 VII 问。

C_{(n-m)+m-1}^{m-1}=C_{n-1}^{m-1}

X

重头戏。

求的就是拆分数。

首先有朴素的和为 n，数的个数为 m 的拆分数 DP：

p_{n,m}=p_{n,m-1}+p_{n-m,m}

滚动数组优化后有 O(n\cdot m) 的复杂度。

听写过题的大佬说，可以用五边形数定理优化 FFT 做，但我不想用 FFT。

有拆分数的生成函数：

\sum_{n=0}^{\infty}p(n)\cdot x^n=P(n)= \prod_{i=1}^{\infty} \frac{1}{1-x^i}

所以有：

\left( \sum_{n=0}^{\infty}p(n)\cdot x^n \right)\cdot \prod_{i=1}^\infty (1-x^i)=1

有欧拉五边形数定理：

\prod_{i=1}^\infty (1-x^i) = 1 + \sum_{k=1}^\infty (-1)^k \cdot \left( x^{\frac{k \cdot (3k-1)}{2}} + x^{\frac{k \cdot (3k+1)}{2}} \right)

其中：\frac{k \cdot (3k-1)}{2}、\frac{k \cdot (3k+1)}{2} 是五边形数。

记广义五边形数为：

b_i= \begin{cases} (-1)^k, &i=\frac{k \cdot (3k\pm 1)}{2}\\ 0, &i\neq\frac{k \cdot (3k\pm 1)}{2} \end{cases}

则：

1 + \sum_{k=1}^\infty (-1)^k \cdot \left( x^{\frac{k \cdot (3k-1)}{2}} + x^{\frac{k \cdot (3k+1)}{2}} \right)=\sum_{k=1}^\infty b_k\cdot x^k

带入：

\left( \sum_{n=0}^{\infty}p(n)\cdot x^n \right)\cdot \left( 1 + \sum_{k=1}^\infty (-1)^k \cdot \left( x^{\frac{k \cdot (3k-1)}{2}} + x^{\frac{k \cdot (3k+1)}{2}} \right) \right)=1

乘开：

\sum_{n=0}^{\infty}\left(\sum_{i=0}^n p(i)\cdot b_{n-i} \right)\cdot x^n=1

对比左右系数：

\sum_{i=0}^n p(i)\cdot b_{n-i}= \begin{cases} 1, &n=0\\ 0, &n\ge 1 \end{cases}

带入 b_i 于是得到：

p(n) + \sum_{k=1}^\infty (-1)^k \left( p\!\left(n - \tfrac{k(3k-1)}{2}\right) + p\!\left(n - \tfrac{k(3k+1)}{2}\right) \right) = 0

所以：

p(n) = \sum_{k=1}^\infty (-1)^{k-1} \left( p\!\left(n - \tfrac{k(3k-1)}{2}\right) + p\!\left(n - \tfrac{k(3k+1)}{2}\right) \right)

但是由于 p(n) 是无限拆分数，但是 m<n 无法无限拆分，所以不能用。

我们注意到复杂度里面带根号，所以考虑分块。

当 m\le \sqrt{n} 直接暴力做。

否则，有拆分数的生成函数：

P_{\le m}(x) = \prod_{i=1}^{m} \frac{1}{1-x^i}

与无限拆分数结合知：

P_{\le m}(x) = P(x) \cdot \prod_{i=m+1}^{\infty} (1-x^i)

对比系数，转化容斥，所以：

p_{\le m}(n) = \sum_{S} (-1)^{|S|} \; p\!\left(n - \sum_{s\in S} s\right)

其中求和遍历所有元素互异，均大于 m 且和不超过 n 的集合是 S。

显然状态是很少的，暴力搜索，枚举子集可以做。

总的时间复杂度是 O(n\cdot \sqrt{n})。

就这样解决了第 X 问。

XI

[n\le m]

显然，自证不难。

XII

是和 X 一样，往每个盒子放一个球后就是 X 了。

::::info[code]

#include<bits/stdc++.h>
using namespace std;

#ifdef ONLINE_JUDGE
#define inline __attribute__((always_inline))
#define debug(x)
#else
#define debug(x) cerr<<#x<<" = "<<x<<"\n";
#endif
#define int long long

const int N=400010,MOD=998244353;

int n,m,fac[N],inv[N],invf[N],p[N],H[N],dp[N];

int qpow(int a,int b,int mod)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int getinv(int x)
{
    x%=MOD;
    if(x<N)
    {
        return inv[x];
    }
    return qpow(x,MOD-2,MOD);
}

int C(int n,int m)
{
    if(m<0||m>n)
    {
        return 0;
    }
    return fac[n]*getinv(fac[m]*fac[n-m]%MOD)%MOD;
}

int s2(int n,int m)
{
    int res=0;
    for(int i=0;i<=m;i++)
    {
        int t=qpow(i,n,MOD)*getinv(fac[i]*fac[m-i]%MOD)%MOD;
        if((m-i)&1)
        {
            res=(res-t+MOD)%MOD;
        }
        else
        {
            res=(res+t)%MOD;
        }
    }
    return res;
}

void init()
{
    inv[0]=inv[1]=fac[0]=invf[0]=1;
    for(int i=2;i<N;i++)
    {
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    for(int i=1;i<N;i++)
    {
        fac[i]=fac[i-1]*i%MOD;
    }
    invf[N-1]=qpow(fac[N-1],MOD-2,MOD);
    for(int i=N-2;i>=1;i--)
    {
        invf[i]=invf[i+1]*(i+1)%MOD;
    }
    H[0]=1;
    for(int i=1;i<N;i++)
    {
        if(i&1)
        {
            H[i]=(H[i-1]-invf[i]+MOD)%MOD;
        }
        else
        {
            H[i]=(H[i-1]+invf[i])%MOD;
        }
    }
    p[0]=1;
    for(int i=1;i<N;i++)
    {
        int res=0;
        for(int k=1;;k++)
        {
            int g1=k*(3*k-1)/2;
            if(g1>i)
            {
                break;
            }
            if(k&1)
            {
                res=(res+p[i-g1])%MOD;
            }
            else
            {
                res=(res-p[i-g1]+MOD)%MOD;
            }
            int g2=k*(3*k+1)/2;
            if(g2>i)
            {
                break;
            }
            if(k&1)
            {
                res=(res+p[i-g2])%MOD;
            }
            else
            {
                res=(res-p[i-g2]+MOD)%MOD;
            }
        }
        p[i]=res;
    }
}

int dp1(int n,int lim)
{
    dp[0]=1;
    for(int i=1;i<=lim;i++)
    {
        for(int j=i;j<=n;j++)
        {
            dp[j]=(dp[j]+dp[j-i])%MOD;
        }
    }
    return dp[n];
}

int dfs2(int st,int sum,int par,int n)
{
    int res=0;
    int sgn=(par&1)?MOD-1:1;
    res=(res+sgn*p[n-sum])%MOD;
    for(int i=st;sum+i<=n;i++)
    {
        res=(res+dfs2(i+1,sum+i,par^1,n))%MOD;
    }
    return res;
}

int solve1(int n,int m)
{
    return qpow(m,n,MOD);
}

int solve2(int n,int m)
{
    if(n>m)
    {
        return 0;
    }
    return fac[m]*getinv(fac[m-n])%MOD;
}

int solve3(int n,int m)
{
    if(n<m)
    {
        return 0;
    }
    int ans=0;
    for(int i=0;i<=m;i++)
    {
        ans+=(i&1?-1:1)*C(m,i)%MOD*qpow(m-i,n,MOD)%MOD;
        ans%=MOD;
    }
    return (ans%MOD+MOD)%MOD;
}

int solve4(int n,int m)
{
    int res=0;
    for(int i=0;i<=m;i++)
    {
        int t=qpow(i,n,MOD)*invf[i]%MOD;
        int val=H[m-i];
        if(i==0)
        {
            val=(val-1+MOD)%MOD;
        }
        res=(res+t*val)%MOD;
    }
    return res;
}

int solve5(int n,int m)
{
    return n<=m;
}

int solve6(int n,int m)
{
    return s2(n,m);
}

int solve7(int n,int m)
{
    return C(n+m-1,m-1);
}

int solve8(int n,int m)
{
    return C(m,n);
}

int solve9(int n,int m)
{
    return C(n-1,m-1);
}

int solve10(int n,int m)
{
    if(m>=n)
    {
        return p[n];
    }
    int B=sqrt(n)+1;
    if(m<=B)
    {
        return dp1(n,m);
    }
    return dfs2(m+1,0,0,n);
}

int solve11(int n,int m)
{
    return n<=m;
}

int solve12(int n,int m)
{
    if(n<m)
    {
        return 0;
    }
    return solve10(n-m,m);
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    cin>>n>>m;
    cout<<solve1(n,m)<<"\n"<<solve2(n,m)<<"\n"<<solve3(n,m)<<"\n"<<solve4(n,m)<<"\n"
        <<solve5(n,m)<<"\n"<<solve6(n,m)<<"\n"<<solve7(n,m)<<"\n"<<solve8(n,m)<<"\n"
        <<solve9(n,m)<<"\n"<<solve10(n,m)<<"\n"<<solve11(n,m)<<"\n"<<solve12(n,m)<<"\n";
    return 0;
}

::::

本题解仅用 AI 完成笔者不会的 LateX 公式，保证 AI 贡献严格小于笔者。