有一种隐忍其实是蕴藏着的一种力量,有一种静默其实是惊天的告白。 题目描述
传说中很多大牛喜欢用自己姓名拼音的重排列,比如著名的吕凯风大牛,他的姓名拼音是lvkaifeng,重新排列之后就得到了VFleaKing,也就是著名的伏特跳蚤国王。现在,火星人觉得VFleaKing太强啦!于是他们也要这样取他们的ID名,现在问题来了,他们的名字都非常长,而且都是由火星文组成的(火星文有好多好多字符)。火星人想请你帮他们算算如果把他们的名字重排有几种方案,当然了,原序列也是一种方案啦~如果你不帮他们算出正确的答案你就会死哦~
形式化描述:给定一个长度为N的整数序列A1…N,求有多少种不同长度为的N的整数序列B1…N是A的重排,即可重集{Ai}={Bi}。两个序列不同当且仅当它们任一位置上的元素不相等。
输入
第1行:两个正整数N,k,其中N代表该火星人名字的长度,k代表火星文有多少种字符,我们不妨设在有k种字符的情况下的火星文中的字符分别是0到k−1。
第2行:用空格隔开的N个正整数,代表这个火星人的名字,我们保证这N个数字一定在0到k−1的范围内。
输出
第1行:一个正整数——这个火星人的名字重排方案数对109+7取模的结果(火星人的逻辑特别奇怪,只要知道模数是多少就可以放过你了)。
样例输入
复制样例数据
4 2
0 0 1 1
样例输出
6
提示
满足条件的重排共有如下6种:
0,0,1,1
0,1,0,1
1,0,0,1
0,1,1,0
1,0,1,0
1,1,0,0
这个题考察排列组合问题,手算结果大家应该都知道怎么算(这个高中学过,就是给你n个m种数让你求排列方式),比如n=7,m=3,数为1,2,1,0,0,2,1,则可知ans=n!/(A(3,3)*A(2,2)*A(2,2))=210,这里除法用逆元实现。
#include