Timus 1114. Boxes 要求計算出將兩種顏色的球放到盒子中的各種組合的數目。

---

1114. Boxes

Time Limit: 0.6 second
Memory Limit: 16 MB

N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B ≤ 15). The red balls (and the blue ones) are exactly the same. You can place the balls in the boxes. It is allowed to put in a box, balls of the two kinds, or only from one kind. You can also leave some of the boxes empty. It's not necessary to place all the balls in the boxes. Write a program, which finds the number of different ways to place the balls in the boxes in the described way.

Input

Input contains one line with three integeres N, A and B separated by space.

Output

The result of your program must be an integer writen on the only line of output.

Sample

inputoutput

2 1 1	9

Problem Source: First competition for selecting the bulgarian IOI team.

---

解答如下(C＃語言)：

?1?using?System;
?2?
?3?namespace?Skyiv.Ben.Timus
?4?{
?5???//?http://acm.timus.ru/problem.aspx?space=1&num=1114
?6???sealed?class?T1114
?7???{
?8?????static?void?Main()
?9?????{
10???????string[]?ss?=?Console.ReadLine().Split();
11???????ulong?n?=?ushort.Parse(ss[0]);
12???????ulong?a?=?ushort.Parse(ss[1]);
13???????ulong?b?=?ushort.Parse(ss[2]);
14???????Console.WriteLine(F(n,?a)?* F(n,?b));
15?????}
16?
17?????static?ulong F(ulong?n,?ulong?m)
18?????{
19???????ulong?v?=?1;
20???????for?(ulong?i?=?1;?i?<=?n;?i++)?v?=?v?*?(m?+?i)?/?i;
21???????return?v;
22?????}
23???}
24?}

這道題就是一個組合數學問題。題目說，你有 N (1 ≤ N ≤ 20) 個盒子，A (0 ≤ A ≤ 15) 個紅色的球和 B (0 ≤ B ≤ 15) 個藍色的球。這些球可以放到盒子里面，也可以不放到盒子里面，一個盒子可以放任意多個球。問總共有多少種不同情形。

由于球可以放到盒子里面，也可以不放到盒子里面，所以紅球和盒子總共有 C( N + A, A ) 種不同的情形。同樣，藍球和盒子總共有 C( N + B, B ) 種不同的情形。所以，最終的答案就是 C( N + A, A) * C( N + B, B ) 。這里，C( n, m ) 表示從 n 個不同的物品中任意取出 m 個的組合數，公式是 C( n, m ) = n! / (n - m)! / m!。以上程序中的 F( n, m ) = C( n + m, m)。

要注意的是，當輸入為 N = 20，A = 15，B = 15 時，輸出是 10549134770590785600，這個數已經大于 2⁶³ - 1，所以要使用 ulong 數據類型。如果使用 C/C++ 語言，因為 Timus Online Judge 使用的是 Visual C++ 編譯器，所以要使用 unsigned __int64 數據類型。如果 在 Sphere Online Judge 答題的話，因為其編譯器是 gcc，所以要使用 unsigned long long 數據類型。C++ 語言的程序如下所示(如果是 gcc 編譯器則去掉第 2 行開頭的“//”)：

?1?#include?<iostream>
?2?//#define?__int64?long?long
?3?
?4?unsigned?__int64 f(unsigned?__int64?n,?unsigned?__int64?m)
?5?{
?6???unsigned?__int64?v?=?1;
?7???for?(unsigned?__int64?i?=?1;?i?<=?n;?i++)?v?=?v?*?(m?+?i)?/?i;
?8???return?v;
?9?}
10?
11?int?main()
12?{
13???unsigned?__int64?n,?a,?b;
14???std::cin?>>?n?>>?a?>>?b;
15???std::cout?<< f(n,?a)?* f(n,?b)?<<?std::endl;
16?}

本程序的運行時間如下：

有點奇怪的是，Visual C++ 編譯器也可以使用 unsigned long long，但是速度卻比使用 unsinged __int64 慢了 15 倍。如上圖所示，ID = 2154601 的記錄就是使用 unsinged long long，運行時間為 0.015 秒。而 ID = 2135962 的記錄使用 unsinged __int64，運行時間為 0.001 秒。不知是什么原因。照理說，__int64 應該和 long long 是一樣的。

總結

以上是生活随笔為你收集整理的Timus 1114. Boxes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。