Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Anagram

Category: JOI Tag: math

Anagram

問題概要


文字列SはSを並び替えた文字列のうち辞書順で何番目にくるか.

解法


Sより前にくる文字列を数える.
0文字目をS[0]以前の文字とした時の並べ方を計算.
1文字目をS[1]以前の文字とした時の並べ方を計算…
としてやればよい. あらかじめ各文字の個数を数えておくと計算しやすい.

コード


(Anagram.cpp) download
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
#include <bits/stdc++.h>
using namespace std;

long long n, fact[32], cnt[32];
string s;

void gen()
{
        fact[0] = 1;
        for (int i = 0; i < n; i++) {
                fact[i+1] = fact[i]*(i+1);
                cnt[s[i]-'A']++;
        }
}

long long comb(int n, int k){ return fact[n]/fact[k]/fact[n-k];}

long long perm(int c, int res)
{
        long long ret = 0;
        for (int i = 0; i < c; i++) {
                long long tmp = 1, r = res;
                if(!cnt[i]) continue;
                cnt[i]--;
                for (int j = 0; j < 26; j++)
                        if(cnt[j]) {
                                tmp *= comb(r,cnt[j]);
                                r -= cnt[j];
                        }
                ret += tmp;
                cnt[i]++;
        }
        return ret;
}

long long solve()
{
        n = s.size();
        gen();
        long long ans = 0;
        for (int i = 0; i < n; i++) {
                int c = s[i] - 'A';
                ans += perm(c, n-i-1);
                cnt[c]--;
        }
        return ans+1;
}

void input()
{
        cin >> s;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments