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过去了，若不知道容斥可能对着道题无从下手。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 long long ans; 6 int n,m; 7 long long Calc(int n,int k){ 8 long long ret=1; 9 for(int i=1;i<=n;i++)ret*=i; 10 for(int i=1;i<=k;i++)ret/=i; 11 for(int i=1;i<=n-k;i++)ret/=i; 12 return ret; 13 } 14 int main(){ 15 freopen("boxball.in","r",stdin); 16 freopen("boxball.out","w",stdout); 17 scanf("%d%d",&n,&m); 18 for(int i=m;i>=1;i--){ 19 long long ret=1; 20 for(int j=1;j<=n;j++) 21 ret*=i; 22 if((m-i+1)&1) 23 ans+=ret*Calc(m,i); 24 else 25 ans-=ret*Calc(m,i); 26 } 27 printf("%lld ",ans); 28 return 0; 29 }