結果

問題 No.3529 2p Teleportations
コンテスト
ユーザー GaLLium
提出日時 2026-03-29 15:00:11
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 1,998 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,992 ms
コンパイル使用メモリ 342,288 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-05-04 20:53:53
合計ジャッジ時間 32,867 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll modinv(ll, ll)':
main.cpp:10:1: warning: control reaches end of non-void function [-Wreturn-type]
   10 | }
      | ^

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll modinv(ll x, ll m){
    if (m == 1) {return 0;}
    for (ll res = 0; res < m; res++){
        if ((res*x) % m == 1) {return res;}
    }
}

void solve(){
    ll N,p; cin >> N >> p;
    vector<ll> A(N+1);
    for (int i = 1; i <= N; i++){
        cin >> A[i];
    }
    
    //サイクルに分解
    vector<vector<vector<ll>>> cycle(N+1);
    vector<bool> seen(N+1,false);
    for (int i = 1; i <= N; i++){
        if (seen[i]) {continue;}
        vector<ll> v;
        while (!seen[i]){
            seen[i] = true;
            v.push_back(i);
            i = A[i];
        }
        cycle[ssize(v)].push_back(v);
    }

    //構築
    vector<ll> B(N+1);
    for (int T = 1; T <= N; T++){
        if (ssize(cycle[T]) == 0){continue;}
        if (T % 2 == 1){
            ll d = modinv(2*p,T);
            while (ssize(cycle[T]) >= 1){
                vector<ll> v = cycle[T].back();
                cycle[T].pop_back();
                for (int k = 0; k < T; k++){
                    B[v[k]] = v[(k-d+T)%T];
                }
            }
        }
        else{
            ll d = modinv(p,T);
            while (ssize(cycle[T]) >= 2){
                vector<ll> u = cycle[T].back();
                cycle[T].pop_back();
                vector<ll> v = cycle[T].back();
                cycle[T].pop_back();
                for (int k = 0; k < T; k++){
                    B[u[k]] = v[k];
                    B[v[k]] = u[(k-d+T)%T];
                }      
            }
            
            if (ssize(cycle[T]) == 0){continue;}
            d = modinv(2*p,T-1);
            vector<ll> v = cycle[T].back();
            for (int k = 0; k < T; k++){
                B[v[k]] = v[(k-d+T-1)%(T-1)];
            }
        }
    }

    for (int i = 1; i <= N; i++){
        cout << B[i];
        if (i == N) {cout << '\n';}
        else {cout << ' ';}
    }      
}

int main(){
    ll T; cin >> T;
    while(T--) {solve();}
}
0