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了一发。。。
/* ***********************************************
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}