HDU 5651 xiaoxin juju needs help

题意：

给你一个字符串，字符任意排列求能组成的回文串数量

首先计算出出现了得字符的出现次数存为num[i],显然有些情况不能组成字符串，比如：1.字符串长度为奇数而所有num[i]均为偶数；2.字符串长度为偶数而所有num[i]均为奇数；3.num[i]为奇数的字符超过两个

为了组成回文串，成对字符肯定分开，排列组合问题， 输出(len/2)! / 所有(num[i]/2)!

问题在于除法如何mod，这里根据费马小定理a^(p-1) mod p = 1,有（a *a^(p-2)）mod p = 1,而(a *1/a) mod p = 1, 故可以用a^(p-2)来代替除数a，所以用到了快速幂

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<stack> #include<algorithm> #include<set> #include<map> #include<deque> using namespace std; #define INF 0x3f3f3f3f typedef long long LL; typedef pair<int,int> ppp; #define MOD 1000000007 char ss[1010]; int num[26]; LL pow_mod(LL sum,LL n){ LL ans = 1; while (n){ if (n&1) ans = ans*sum%MOD; sum = sum*sum%MOD; n>>=1; } return ans; } LL work(int x){ LL now = 1; for (int i=1 ; i<=num[x]/2 ; i++) now = now*i%MOD; return pow_mod(now%MOD,MOD-2); } int main(){ int T; scanf("%d",&T); while (T--){ scanf("%s",ss); int len = strlen(ss); memset(num,0,sizeof num); for (int i=0 ; i<len ; i++) num[ss[i]-'a']++; int flag = 0; for (int i=0 ; i<26 ; i++) if (num[i]%2) flag++; if ((len%2&&!flag) || (len%2==0&&flag) || (flag>2)) printf("0\n"); else if (len==1) printf("1\n"); else { LL ans = 1; for (int i=len/2 ; i>=1 ; i--){ ans = ans*i%MOD; } for (int i=0 ; i<26 ; i++) if (num[i]){ ans = ans*work(i)%MOD; } printf("%d\n",(int)ans%MOD); } } return 0; }