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

2016-03-27 · 2 min read · 排列组合 逆元

题目链接 题意；给出一个字符串，只由小写字母组成，可以任意排列，但是不能减少字符，问最多能得到多少个回文串，答案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了一发。。。

/* ***********************************************
Author :111qqz
Created Time :2016年03月26日 星期六 18时52分01秒
File Name :code/bc/#77/1001.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const LL MOD =1E9+7;
 7const int N=1E3+9;
 8string s;
 9int cnt[30]; //start from 1
10LL ny[N];
11LL fac[30];

1bool cmp( int a,int b)
2{
3    return a>b;
4}

 1LL ksm(LL a,LL b)
 2{
 3    LL res=1LL;
 4    while (b>0)
 5    {
 6	if (b%2==1) res = (res*a)%MOD;
 7	b = b>>1;
 8	a = (a*a)%MOD;
 9    }
10    return res;
11}

1void getny()
2{
3    ms(ny,0);
4    for ( int i = 1 ; i <= 1004 ;  i++)
5	ny[i] = ksm(LL(i),MOD-2);
6}

1int main()
2{
3	#ifndef  ONLINE_JUDGE 
4	freopen("code/in.txt","r",stdin);
5  #endif

 1//	getny();
 2	int T;
 3	cin>>T;
 4	while (T--)
 5	{
 6	    cin>>s;
 7	    ms(cnt,0);
 8	    int len = s.length();
 9	    for ( int i = 0 ; i < len;  i++)
10	    {
11		int tmp = s[i]-'a'+1;
12		cnt[tmp]++;
13	    }

 1	    int odd = 0 ;
 2	    int even = 0 ;
 3	    for ( int i = 1 ; i <= 26 ; i++)
 4	    {
 5		if (cnt[i]==0) continue;
 6		if (cnt[i]%2==0) even++;
 7		else odd++;
 8	    }
 9	    if (len%2==1&&odd>1)
10	    {
11		printf("0\n");
12		continue;
13	    }
14	    if (len%2==0&&odd>0)
15	    {
16		printf("0\n");
17		continue;
18	    }

	    sort(cnt+1,cnt+27,cmp);

 1	    int p;
 2	    for ( int i = 1 ; i <= 26 ; i++)
 3	    {
 4		if (cnt[i]<=1)
 5		{
 6		    p = i-1;
 7		    break;
 8		}
 9		cnt[i] = cnt[i] / 2;
10	    }
11//	    cout<<"p:"<<p<<endl;
12	    int hl = len/2;
13	    LL ans = 1LL;
14	    for ( LL i = 1 ; i <= hl ; i++) ans = (ans * i)%MOD;
15//	    cout<<"ans1:"<<ans<<endl;

 1	    for ( int i = 1 ; i <= p ; i++)
 2	    {
 3		fac[i] = 1LL;
 4		for ( LL j = 2 ; j <= LL(cnt[i]) ; j++)
 5		{
 6		    fac[i] = (fac[i] * j)%MOD;
 7		}
 8	    }
 9	    for ( int i = 1 ; i <= p ; i++)
10	    {
11		LL tmpny = ksm(fac[i],MOD-2);
12		ans = (ans * tmpny)%MOD;
13	    }
14	    ans = ans % MOD;
15	    printf("%I64d\n",ans);
16	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}