题目链接
题目思路
标题就不难知道，这是一道关于容斥原理的题目
只需要简单一想就不难发现，这道题很可能会有很多重复的情况，就比如说我原来想的一个思路，先找出 r 个球来铺满第一层，然后再排列剩下的小球，这就会有很多重复的情况，比如说第一层的去了第二层，但是只是上下顺序变了但是总体顺序没变，这就造成了重复的情况
那么我们不妨反过来想
n 个小球放到 r 个盒子里一共有多少种放法呢？
一想就能想到
方案数
=
r
n
方案数 = r^n
方案数=rn
因为每个小球都有r个盒子可以放，所有就是n个r相乘
那么至少一个盒子是空着的呢？
结果也是显而易见的
方案数
=
C
r
1
∗
(
r
−
1
)
n
方案数 = C_r^1 * (r - 1)^n
方案数=Cr1∗(r−1)n
一共有r个盒子，并且互不相同，所以哪个是空的不确定，由于是至少一个盒子是空的，所以就是每个小球有r-1个盒子可以放，也就是n个r-1相乘
这个时候你应该就能发现后面的规律了
至少o个盒子是空着的情况就是
方案数
=
C
r
o
∗
(
r
−
o
)
n
方案数 = C_r^o * (r - o)^n
方案数=Cro∗(r−o)n
但是此时的你可能还不是很理解要干嘛
不是这样还是有很多重复的情况吗？
这里就涉及到了一个重要的组合数学原理，容斥原理
定义：若A和B是具有性质P1和性质P2的有限集合
那么 A ∪ B = A + B − A ∩ B A ∪ B = A + B - A ∩ B A∪B=A+B−A∩B
同理可得 $A ∪ B ∪ C = A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C $
通俗易懂的来说接下来的步骤就是用总情况， 减去 至少有一个的时候， 加上 至少有2个的时候 。。。。。。
再解释一下就是减去所有至少有一个的情况的时候，就多减去了很多至少有2个的时候，加上的时候又加上了很多至少有三个的情况，以此类推
那么剩下的就是组合数学的基础部分，快速幂就不展开了，组合数由于范围非常小，如果又不理解的朋友可以转去看我的这篇文章
(组合数的计算)牛客周赛 Round 35 小红的子序列权值和 (easy / hard)
总代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15;
int n,r;
int C[N][N];
int init()
{
for(int i=0;i<N;i++){
for(int j=0;j<=i;j++){
if(!j) C[j][i] = 1;
else C[j][i] = C[j-1][i-1] + C[j][i-1];
}
}
}
int qmi(int a,int b)
{
int res = 1;
while (b){
if(b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
signed main()
{
init();
cin >> n >> r;
int o = qmi(r,n);
for(int i=1;i<r;i++){
if(i & 1){
o -= C[i][r] * qmi(r-i,n);
}else{
o += C[i][r] * qmi(r-i,n);
}
}
cout << o << endl;
}