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 
     
       2 #include 
      
        3 #include 
       
         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\n",ans);    28     return 0;29 }