Problem Solving►UVa

UVa 153 - Permalex

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

一開始用回溯做，想當然超時了。查了一下發現這個 康托展開。

簡單來說就是計算此字串的順序。以每個比當前字母小的來當作替換，找出有幾種可能並相加。要注意有字母一樣時的處理。

舉例來說: bacaa

“b” acaa ，可用 a 來做替換， “a”bcaa 、 “a”abca …等組合，總共為 $\frac{4!}{2!}$ 種，$4!$ 為 “a” 後面有幾個字母， $2!$ 為後面 a 重複的有兩個。

b “a” caa ，沒有可替換的。

ba “c” aa ，可用 a 來做替換，ba “a” ac …，總共 $2!$ 。

最後相加起來，則為在此字串前有幾種不同的組合。
此字串的順序為: $\frac{4!}{2!}+2!+1$，要 +1 才會是當前的。

而因為有可能在計算階乘時溢位，所以我們用一個陣列 num[] 來存階乘的每個數，再分別去做約分:

for (int c = 2; c <= alp[k]; c++)//分母
{
    int temp = c;
    for (int n = 2; n <= back&&temp > 1; n++)//分子
    {
    int g = gcd(temp, num[n]);
    temp /= g;
    num[n] /= g;
    }
}

最後把它們乘起來:

LL result = 1;
for (k = 2; k <= back; k++)
    result *= num[k];

就可得出以其中一個較小字母做替換時的組合數了。

Code

UVa 153UVa 153 - Permalex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<cstring>
#define N 31
typedef long long LL;
inline int gcd(int a, int b);
int main()
{
    char str[N];
    while (gets(str) && str[0] != '#')
    {
        int i, j, k, len = strlen(str);
        int alp[26] = {};

        //計算字母數
        for (i = 0; i < len; i++)
            alp[str[i] - 'a']++;

        LL ans = 0;
        for (i = 0; i < len; i++)
        {
            for (j = 0; j < str[i] - 'a'; j++)//每個小於 str[i] 的字母
            {
                if (!alp[j])
                    continue;

                int back = len - i - 1;//str[i] 後方的字母個數
                
                alp[j]--;//以 j + 'a' (字母)當頭

                //分子
                int num[N] = {};
                for (k = 0; k <= back; k++)
                    num[k] = k;

                //處理相同字母多於一時
                for (k = 0; k < 26; k++)
                {
                    for (int c = 2; c <= alp[k]; c++)//要除的分母
                    {
                        int temp = c;
                        for (int n = 2; n <= back&&temp > 1; n++)//分子
                        {
                            //防止溢位，邊乘邊約分
                            int g = gcd(temp, num[n]);
                            temp /= g;
                            num[n] /= g;
                        }
                    }
                }

                alp[j]++;//歸位

                //計算以每個小於str[i]的字母做替換的組合數
                LL result = 1;
                for (k = 2; k <= back; k++)
                    result *= num[k];
                ans += result;
            }

            alp[str[i] - 'a']--;//此字母已被計算完成
        }

        printf("%10lld\n", ans + 1);
    }


    return 0;
}
int gcd(int a, int b)
{
    while (a)
    {
        int temp = a;
        a = b%a;
        b = temp;
    }

    return b;
}