logo AlgoBeat OnlineJudge
登录 注册

#102023. [BZOJ 2023] [Usaco2005 Nov]Ant Counting 数蚂蚁

内存限制:64 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一天,贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物。很快贝茜发现有些蚂蚁长得几乎一模一样,于是她认为那些蚂蚁是兄弟,也就是说它们是同一个家族里的成员。她也发现整个蚂蚁群里有时只有一只出来觅食,有时是几只,有时干脆整个蚁群一起出来。这样一来,蚂蚁们出行觅食时的组队方案就有很多种。作为一头有数学头脑的奶牛,贝茜注意到整个蚂蚁群由 个家族组成,她将这些家族按 依次编号。编号为 的家族里有 只蚂蚁。同一个家族里的蚂蚁可以认为是完全相同的。如果一共有 只蚂蚁一起出去觅食,它们一共能组成多少种不同的队伍呢?注意:只要两支队伍中所包含某个家族的蚂蚁数不同,我们就认为这两支队伍不同。由于贝茜无法分辨出同一家族的蚂蚁,所以当两支队伍中所包含的所有家族的蚂蚁数都相同时,即使有某个家族换了几只蚂蚁出来,贝茜也会因为看不出不同而把它们认为是同一支队伍。比如说,有个由 个家族组成的蚂蚁群里一共有 只蚂蚁,它们所属的家族分别为 。于是出去觅食时它们有以下几种组队方案:

  • 只蚂蚁出去有三种组合:
  • 只蚂蚁出去有五种组合:
  • 只蚂蚁出去有五种组合:
  • 只蚂蚁出去有三种组合:
  • 只蚂蚁出去有一种组合:

你的任务就是根据给出的数据,计算蚂蚁们组队方案的总数。

输入格式

第一行: 个用空格隔开的整数

第二行到第 行:每行是一个正整数,为某只蚂蚁所在的家族的编号。

输出格式

输出一个整数,表示当 (包括 )只蚂蚁出去觅食时,不同的组队方案数。

注意:组合是无序的,也就是说组合 和组合 是同一种组队方式。最后的答案可能很大,你只需要输出答案的最后 位数字,注意不要输出前导 以及多余的空格。

样例

样例输入 #1

5 2 3

样例输出 #1

10

样例说明 1

只蚂蚁外出有 种组合, 只蚂蚁外出有 种组合。共有 种组合。

数据范围与提示

对于 的数据,

Silver