Submission

Score: 100

User: porpeang

Problemset: สุ่มสลับ

Language: cpp

Time: 0.002 second

Submitted On: 2026-10-05 22:14:25

#include <iostream>
#include <string>

using namespace std;

// ตารางเก็บค่า Factorial ล่วงหน้า (O(1) Lookup)
const long long FACT[] = {
    1,          // 0!
    1,          // 1!
    2,          // 2!
    6,          // 3!
    24,         // 4!
    120,        // 5!
    720,        // 6!
    5040,       // 7!
    40320,      // 8!
    362880,     // 9!
    3628800,    // 10!
    39916800,   // 11!
    479001600   // 12!
};

int main() {
    // เร่งการทำงานของ I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    string s;
    cin >> s;

    // Bitmask เก็บตัวอักษรที่ยังไม่ได้ใช้ (เปิดบิตเป็น 1 ทั้งหมด N บิต)
    int mask = (1 << N) - 1;
    long long rank = 1;

    for (int i = 0; i < N; i++) {
        int char_idx = s[i] - 'A';

        // นับจำนวนตัวอักษรที่น้อยกว่า s[i] และยังไม่ถูกใช้ใน O(1)
        int smaller_unused_mask = mask & ((1 << char_idx) - 1);
        int count_smaller = __builtin_popcount(smaller_unused_mask);

        // คำนวณลำดับเพิ่ม
        rank += count_smaller * FACT[N - 1 - i];

        // ปิดบิตตัวอักษรที่ถูกใช้ไปแล้ว
        mask &= ~(1 << char_idx);
    }

    cout << rank << "\n";

    return 0;
}