結果

問題 No.1311 Reverse Permutation Index
コンテスト
ユーザー pes_magic
提出日時 2020-12-20 16:19:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 1,090 bytes
コンパイル時間 666 ms
コンパイル使用メモリ 75,632 KB
最終ジャッジ日時 2025-01-17 04:52:37
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;

long long getOrder(const vector<int>& v){
    const int N = v.size();
    vector<int> used(N+1, 0);
    long long res = 0;
    for(int i=0;i<N-1;i++){
        res *= N-i;
        int add = v[i]-1;
        for(int j=1;j<v[i];j++) add -= used[j];
        used[v[i]] = 1;
        res += add;
    }
    return res;
}

vector<int> getPerm(long long s, int N){
    vector<long long> fact(N);
    fact[0] = fact[1] = 1;
    for(int i=2;i<N;i++) fact[i] = i * fact[i-1];
    vector<int> used(N, 0);
    vector<int> res;
    for(int i=0;i<N;i++){
        int ord = s/fact[N-1-i];
        s %= fact[N-1-i];
        for(int j=0;j<N;j++){
            if(used[j]) continue;
            if(ord == 0){
                res.push_back(j+1);
                used[j] = 1;
                break;
            }
            --ord;
        }
    }
    return res;
}


int main(){
    int N;
    long long S;
    cin >> S >> N;
    auto v = getPerm(S, N);
    vector<int> r(N);
    for(int i=0;i<N;i++) r[v[i]-1] = i+1;
    cout << getOrder(r) << endl;
}
0