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}

相关文章