个人训练赛第十七场问题D:vfk式名字重排

题目描述

传说中很多大牛喜欢用自己姓名拼音的重排列&＃xff0c;比如著名的吕凯风大牛&＃xff0c;他的姓名拼音是lvkaifeng&＃xff0c;重新排列之后就得到了VFleaKing&＃xff0c;也就是著名的伏特跳蚤国王。现在&＃xff0c;火星人觉得VFleaKing太强啦&＃xff01;于是他们也要这样取他们的ID名&＃xff0c;现在问题来了&＃xff0c;他们的名字都非常长&＃xff0c;而且都是由火星文组成的&＃xff08;火星文有好多好多字符&＃xff09;。火星人想请你帮他们算算如果把他们的名字重排有几种方案&＃xff0c;当然了&＃xff0c;原序列也是一种方案啦~如果你不帮他们算出正确的答案你就会死哦~

形式化描述&＃xff1a;给定一个长度为N的整数序列A1…N&＃xff0c;求有多少种不同长度为的N的整数序列B1…N是A的重排&＃xff0c;即可重集{Ai}&＃61;{Bi}。两个序列不同当且仅当它们任一位置上的元素不相等。

输入

第1行&＃xff1a;两个正整数N,k&＃xff0c;其中N代表该火星人名字的长度&＃xff0c;k代表火星文有多少种字符&＃xff0c;我们不妨设在有k种字符的情况下的火星文中的字符分别是0到k−1。
第2行&＃xff1a;用空格隔开的N个正整数&＃xff0c;代表这个火星人的名字&＃xff0c;我们保证这N个数字一定在0到k−1的范围内。

输出

第1行&＃xff1a;一个正整数——这个火星人的名字重排方案数对109&＃43;7取模的结果&＃xff08;火星人的逻辑特别奇怪&＃xff0c;只要知道模数是多少就可以放过你了&＃xff09;。

样例输入

复制样例数据

4 2
0 0 1 1

样例输出

6

提示

满足条件的重排共有如下6种&＃xff1a;
0,0,1,1
0,1,0,1
1,0,0,1
0,1,1,0
1,0,1,0
1,1,0,0

这个题考察排列组合问题&＃xff0c;手算结果大家应该都知道怎么算&＃xff08;这个高中学过&＃xff0c;就是给你n个m种数让你求排列方式&＃xff09;&＃xff0c;比如n&＃61;7&＃xff0c;m&＃61;3&＃xff0c;数为1&＃xff0c;2&＃xff0c;1&＃xff0c;0&＃xff0c;0&＃xff0c;2&＃xff0c;1&＃xff0c;则可知ans&＃61;n!/(A(3,3)*A(2,2)*A(2,2))&＃61;210&＃xff0c;这里除法用逆元实现。

#include