CF101532K Palindromes Building(暴力模拟)

题面：

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once, such as "post", "stop", and "spot".

You are given a string s consisting of lowercase English letters. Your task is to count how many distinct anagrams of the string s are palindromes.

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".

For example, "aabb" has 6 distinct anagrams, which are: "aabb", "abab", "abba", "baab", "baba", "bbaa". Two of the previous anagrams are palindromes, which are: "abba", "baab".

 

Input：

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 20), where n is the length of the string s.

The second line of each test contains a string s of length n consisting of lowercase English letters.

 

Output：

For each test case, print a single line containing how many distinct anagrams of the string s are palindromes.

 

Example：

 

 

分析：

我感觉我真是弱回文串……好像除了杭电那道入门题之外我还从来没做对过一道回文串的题，看见就脑壳痛，但是没有办法，生活所迫，迟早还是要去啃的。据大佬指点是一道排列组合题，黑板上排列组合，我果然还是解不开。首先根据n的奇偶性判断能不能产生回文串，如果n为偶数，那么每种字母出现的次数都要为偶数才会出现回文串，如果n是奇数，那么有且必须有一种字母的出现次数为奇数，其余字母都出现偶数次。判断了之后用排列组合来算回文串种类，因为是回文所以从中间为轴对称，只算前半段的情况就行了，如果是总偶数个，那么不存在正中间的数，如果是总奇数个，那么中间的字母是固定的，必须是出现次数为奇数的那种字母，所以也可以直接用n/2的方式来算前半段，刚好可以把那0.5去尾。

前半段总的排列情况就是(n/2)!，其中重复的情况就是字母相同排列互换，比如两个a，aa和aa就是重复的情况，都算在(n/2)!里了，所以要除以每一种字母的(num[i]/2)!，考虑到会不会爆int，用了long long， 不过用没用上我不确定。

然而最后还是一直有点小问题，找了半天发现出在memset上……memset(num,sizeof(num),0)这个也太丢人了……我果然是memset都写不对了啊。

 

AC代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int t, n;
int num[26];
bool flag;

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		string str;
		cin>>str;
		memset(num, 0, sizeof(num));
		flag = true;
		
		for(int i = 0; i < n; i++){
			num[str[i] - 'a']++;
		}
		
		if(n % 2 == 0){
			for(int i = 0; i < 26; i++) {
				if(num[i] % 2 != 0) {
					flag = false;
					break;
				}
			}
		}
		else{
			int u = 0;
			for(int i = 0; i < 26; i++){
				if(num[i] % 2 == 1) u++;
			}
			if(u != 1) flag = false;
		}
		
		if(!flag){
			cout<<0<<endl;
			continue;
		}
		
		long long temp = 1, tempp = 1;
		
		for(int i = 1; i <= (n / 2); i++) temp *= i;
		
		for(int i = 0; i < 26; i++){
			if(num[i])
				for(int j = 1; j <= (num[i] / 2); j++) 
					tempp *= j;
		}

		cout<<temp / tempp<<endl;
	}
	return 0;
}