P1287 盒子与球

· · 题解

这几天容斥原理有点上头了，看到这个题目的题解里没有这么做的，就来水发题解。

正文开始。

首先，题面极为简洁，无需翻译，这边搬运一下：

我们先来考虑这一种情况：

如果这样，是不是就很好做了呢？

答案就是 m^n，因为每一个小球的决策都不影响其他小球。

那我们再来看这一种情况：

也没有什么难度，我们只要先选出哪些盒子是必须空的，再让剩下的随意分配即可。

答案：\operatorname C_m^k\times(m-k)^n

然后就是重点内容：容斥原理。

我们回到原题，如此考虑：

只需将随意分配的结果个数减去有空盒的即可。

而有空盒的又可以这么分：一个空盒、两个空盒……

所以我们引入这样一个柿子：

\sum_{i=1}^m{(-1)^{i-1}}\operatorname C_m^i(m-i)^n

这就是有空盒的结果个数，是著名的容斥原理的一种应用。

我们只要用 m^n 减去这个柿子，就是我们的答案。

但是，这两个东西可以合在一起：

\begin{aligned}&m^n-\sum_{i=1}^m{(-1)^{i-1}}\mathrm C_m^i(m-i)^n \\ =\ & m^n+\sum_{i=1}^m{(-1)^i}\mathrm C_m^i(m-i)^n \\ =\ &(-1)^0\operatorname C_m^0(m-0)^n+\sum_{i=1}^m{(-1)^i}\operatorname C_m^i(m-i)^n \\ =\ &\sum_{i=0}^m{(-1)^i}\operatorname C_m^i(m-i)^n \\\end{aligned}

这就是最终的结果计算式。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long n){
    long long ans=1;
    while(n){
        if(n%2)ans*=a;
        a*=a;
        n>>=1;
    }
    return ans;
}
long long C(long long a,long long b){
    long long ans=1;
    for(long long i=a-b+1;i<=a;++i)ans=ans*i;
    for(long long i=1;i<=b;++i)ans=ans/i;
    return ans;
}
int main(){
    long long a,b;
    cin>>a>>b;
    long long ans=0;
    for(long long i=0;i<b;++i){
        if(i&1)ans-=C(b,i)*qpow(b-i,a);
        else ans+=C(b,i)*qpow(b-i,a);
    }
    cout<<ans;
    return 0;
}