列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

NPSC 2004 高中組 初賽 A.迴文數目

說明：迴文就是一個字串反轉後，會和原本的字串一樣，也就是左右對稱。現在給你幾個字串，請你計算每個字串的全排列中有多少個迴文。

解法：要知道一個字串的全排列有沒有迴文，要先計算每個字元出現的次數。如果所有字元出現的次數都是偶數，則我們把它們分兩半，一半放在字串的前面，另一半放在字串的後面，接下來計算前面這一半有多少種排序(重覆排列)，而後面這一半則是和前面那一半相反，所以不用理它。

而如果出現次數有一個是奇數，則迴文的正中央那個字元一定就是那個寄數的字元，剩下的就同前面全部偶數的計算方式。但是如果有兩個字元以上的出現次數是奇數，則不可能有迴文出現。

參考程式：(By sagit)

代碼: [選擇]

// NPSC 2004 初賽 - 題目 A - 迴文數目 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#define LEN 41
#define LEN2 21

using namespace std;

long long int N[LEN2];
// 記錄 N! 的值

// 計算 N! 的值
void Init()
{
    int i;
    N[0]=1;
    for (i=1; i<LEN2; i++)
        N[i]=N[i-1]*i;
}

// 計算字串 s 的迴文個數
long long int R(char s[])
{
    char c[LEN];
    int a[LEN], n, i, j, p;
    long long int l;
    // 計算各個字元出現的次數
    for (i=0, n=0; s[i]; i++)
    {
        for (j=0; j<n; j++)
            if (s[i]==c[j]) break;
        if (j<n) a[j]++;
        else
        {
            c[n]=s[i];
            a[n]=1;
            n++;
        }
    }
    l=N[i/2]; // i 為字串長度
    for (i=0, p=0; i<n; i++)
    {
        // 計算出現次數為奇數的個數
        if (a[i]%2)
        {
            p++;
            // 有兩個以上字元的出現個數為奇數, 則不可能有迴文
            if (p>1) return 0;
        }
        a[i]/=2;
        l/=N[a[i]];
    }
    return l;
}

int main()
{
    ifstream fin("pa.in");
    ofstream fout("pa.out");
    int n, i;
    char s[LEN];

    Init();
    fin >> n;
    for (i=0; i<n; i++)
    {
        fin >> s;
        fout << R(s) << endl;
    }

//    system("PAUSE");
    return 0;
}