bc #77 div 2 B ||hdu 5651 xiaoxin juju needs help (排列组合，逆元)
题目链接 题意；给出一个字符串，只由小写字母组成，可以任意排列，但是不能减少字符，问最多能得到多少个回文串，答案9+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了一发。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月26日 星期六 18时52分01秒
4File Name :code/bc/#77/1001.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const LL MOD =1E9+7;
34const int N=1E3+9;
35string s;
36int cnt[30]; //start from 1
37LL ny[N];
38LL fac[30];
39
40bool cmp( int a,int b)
41{
42 return a>b;
43}
44
45
46LL ksm(LL a,LL b)
47{
48 LL res=1LL;
49 while (b>0)
50 {
51 if (b%2==1) res = (res*a)%MOD;
52 b = b>>1;
53 a = (a*a)%MOD;
54 }
55 return res;
56}
57
58void getny()
59{
60 ms(ny,0);
61 for ( int i = 1 ; i <= 1004 ; i++)
62 ny[i] = ksm(LL(i),MOD-2);
63}
64
65int main()
66{
67 #ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69 #endif
70
71// getny();
72 int T;
73 cin>>T;
74 while (T--)
75 {
76 cin>>s;
77 ms(cnt,0);
78 int len = s.length();
79 for ( int i = 0 ; i < len; i++)
80 {
81 int tmp = s[i]-'a'+1;
82 cnt[tmp]++;
83 }
84
85 int odd = 0 ;
86 int even = 0 ;
87 for ( int i = 1 ; i <= 26 ; i++)
88 {
89 if (cnt[i]==0) continue;
90 if (cnt[i]%2==0) even++;
91 else odd++;
92 }
93 if (len%2==1&&odd>1)
94 {
95 printf("0\n");
96 continue;
97 }
98 if (len%2==0&&odd>0)
99 {
100 printf("0\n");
101 continue;
102 }
103
104 sort(cnt+1,cnt+27,cmp);
105
106 int p;
107 for ( int i = 1 ; i <= 26 ; i++)
108 {
109 if (cnt[i]<=1)
110 {
111 p = i-1;
112 break;
113 }
114 cnt[i] = cnt[i] / 2;
115 }
116// cout<<"p:"<<p<<endl;
117 int hl = len/2;
118 LL ans = 1LL;
119 for ( LL i = 1 ; i <= hl ; i++) ans = (ans * i)%MOD;
120// cout<<"ans1:"<<ans<<endl;
121
122 for ( int i = 1 ; i <= p ; i++)
123 {
124 fac[i] = 1LL;
125 for ( LL j = 2 ; j <= LL(cnt[i]) ; j++)
126 {
127 fac[i] = (fac[i] * j)%MOD;
128 }
129 }
130 for ( int i = 1 ; i <= p ; i++)
131 {
132 LL tmpny = ksm(fac[i],MOD-2);
133 ans = (ans * tmpny)%MOD;
134 }
135 ans = ans % MOD;
136 printf("%I64d\n",ans);
137 }
138
139 #ifndef ONLINE_JUDGE
140 fclose(stdin);
141 #endif
142 return 0;
143}