1220. 盒子与球
★ 输入文件：boxball.in 输出文件：boxball.out 简单对比
时间限制：1 s
内存限制：128 MB
【问题描述】
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子。问有多少种方法？
例如：有2个不同的盒子（分别编为1号和2号）和3个不同的球（分别编为1、2、3号），则有6种不同的方法：
|
1号盒子 |
1号球 |
1、2号球 |
1、3号球 |
2号球 |
2、3号球 |
3号球 |
|
2号盒子 |
2、3号球 |
3号球 |
2号球 |
1、3号球 |
1号球 |
1、2号球 |
【输入】
两个整数，n和r，中间用空格分隔。（0≤n, r≤10）
【输出】
仅一行，一个整数（保证在长整型范围内）。表示n个球放入r个盒子的方法。
【样例】
box.in
3 2
box.out
6
容斥就可以A过去了，若不知道容斥可能对着道题无从下手。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long long ans;
int n,m;
long long Calc(int n,int k){
long long ret=;
for(int i=;i<=n;i++)ret*=i;
for(int i=;i<=k;i++)ret/=i;
for(int i=;i<=n-k;i++)ret/=i;
return ret;
}
int main(){
freopen("boxball.in","r",stdin);
freopen("boxball.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=m;i>=;i--){
long long ret=;
for(int j=;j<=n;j++)
ret*=i;
if((m-i+)&)
ans+=ret*Calc(m,i);
else
ans-=ret*Calc(m,i);
}
printf("%lld\n",ans);
return ;
}