bc #77 div 2 B ||hdu 5651 xiaoxin juju needs help (排列组合,逆元)

题目链接
题意;给出一个字符串,只由小写字母组成,可以任意排列,但是不能减少字符,问最多能得到多少个回文串,答案%1E9+7

思路:排列组合题。 首先考虑无解的情况。统计出每个字母出现的次数,当字符串长度为奇数而且出现次数为奇数的字母的个数多于1个时无解,或者当字符串长度为偶数,出现次数为奇数的字母的个数多于0个时无解。
接下来,由于是回文串,只需要考虑len/2的情况,另一半是一一对应的。
其实就是一共有len/2的元素,其中有一些重复的,然后全排列。 多重元素的排列问题。
答案为(len/2)! % (cnt[1]!)% (cnt[2]!)…即可
哦要先把cnt降序排一下,只考虑cnt[i]>1的元素,然后因为是要考虑一半长度,所以每个cnt[i]/2
那一堆阶乘直接逆元搞就好了。。。。

比赛的时候手滑,把cnt[i]!写成了cnt[i],wa了一发。。。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz