【題解】TIOJ 2052 . 排列第幾個?(Permutation)

【題目敘述】https://tioj.ck.tp.edu.tw/problems/2052

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int d, ans, c[1025][1025];
string s;
map <char, int> mp;

int gcd(int x, int y){
    if (y == 0) return x;
    return gcd(y, x%y);
}

int main() {
    cin >> d >> s;
    for (int i = 0; i < s.length(); i++){
        mp[s[i]]++;
    }
    for (int i = 0; i <= 1024; i++){
        c[i][0] = 1;
        for (int j = 1; j <= i; j++){
            c[i][j] = (c[i-1][j]+c[i-1][j-1])%d;
        }
    }
    for (int i = 0; i < s.length(); i++){
        for (auto &j:mp){
            if (j.first == s[i]) break;
            int tmp = 1;
            j.second--;
            int left = s.length()-i-1;
            for (auto k:mp){
                tmp *= c[left][k.second];
                tmp %= d;
                left -= k.second;
            }
            j.second++;
            ans += tmp;
            ans %= d;
        }
        mp[s[i]]--;
        if (mp[s[i]] == 0) mp.erase(s[i]);
    }
    cout << ans << "\n";
}

分享本文 Share with friends