CF1716F Bags with Balls 题解

· · 题解

每个袋子有 \left \lceil \frac{m}{2} \right \rceil 个奇数编号的球，有 \left \lfloor \frac{m}{2} \right \rfloor 个偶数编号的球，综合一下题意，可以发现此题实际是在求：

\sum_{i=0}^{n}i^k \binom{n}{i} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}

首先考虑处理式子中的 i^k，我们可以利用第二类斯特林数将常幂展开为下降幂求和的方法：

i^k=\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix}j!\binom{i}{j} =\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix}i^{\underline j}

代入原式：

\sum_{i=0}^{n}i^k \binom{n}{i} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i} =\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix}i^{\underline j}\binom{n}{i} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}

因为

\binom{n}{i}i^{\underline j}=\binom{n-j}{i-j}n^{\underline j}

所以式子又可以化成：

=\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix}\binom{n-j}{i-j}n^{\underline j} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}

注意到

\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j}

这个部分与 i 并没有关系，所以可以把这部分提到前面：

\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j}\sum_{i=0}^{n}\binom{n-j}{n-i} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}

最后，我们可以用二项式定理化到最简，最简式子：

\sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix}n^{\underline j}\left ( \left \lceil \frac{m}{2} \right \rceil \right ) ^j m^{n-j}

综上，我们可以 O(k^2) 递推第二类斯特林数，单次查询 O(k)，足以通过此题。

递推代码：

stir[0][0]=1;
for(int i=1;i<=2000;++i){
    for(int j=1;j<=i;++j) stir[i][j]=(stir[i-1][j-1]+stir[i-1][j]*j%mod)%mod;
}

查询代码：

inline ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;a=a*a%mod;
    }
    return res;
}
inline void solve(){
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    ll base=qpow(m,n),inv=qpow(m,mod-2);
    for(int i=1;i<=min(n,k);++i){
        base=base*(n-i+1)%mod*((m+1)/2)%mod*inv%mod;
        ans=(ans+base*stir[k][i]%mod)%mod;
    }
    cout<<ans<<'\n';
}