結果

問題 No.261 ぐるぐるぐるぐる！あみだくじ！
コンテスト
ユーザー mamekin
提出日時 2016-10-09 21:57:42
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,865 bytes
記録
コンパイル時間 1,270 ms
コンパイル使用メモリ 110,268 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 00:25:34
合計ジャッジ時間 2,555 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

long long gcd(long long a, long long b){
    while(b != 0){
        long long tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

long long extgcd(long long a, long long b, long long &x, long long &y) {
    long long g = a;
    if(b != 0){
        g = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return g;
}

long long mod_inverse(long long a, long long m)
{
    long long x, y;
    extgcd(a, m, x, y);
    return (x % m + m) % m;
}

pair<long long, long long> ChineseRemainderTheorem(const vector<int>& a, const vector<int>& b, const vector<int>& m)
{
    pair<long long, long long> ret(0, 1);

    for(unsigned i=0; i<a.size(); ++i){
        long long s = a[i] * ret.second;
        long long t = b[i] - a[i] * ret.first;
        long long d = gcd(m[i], s);
        if(t % d != 0)
            return make_pair(-1, -1);
        long long u = t / d * mod_inverse(s / d, m[i] / d) % (m[i] / d);
        ret.first += ret.second * u;
        ret.second *= m[i] / d;
        ret.first = (ret.first % ret.second + ret.second) % ret.second;
    }

    return ret;
}

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> from(n);
    for(int i=0; i<n; ++i)
        from[i] = i;
    for(int i=0; i<k; ++i){
        int x, y;
        cin >> x >> y;
        swap(from[x-1], from[y-1]);
    }
    vector<int> to(n);
    for(int i=0; i<n; ++i)
        to[from[i]] = i;

    vector<vector<int> > cycle(n);
    for(int i=0; i<n; ++i){
        cycle[i].push_back(i);
        while(to[cycle[i].back()] != i)
            cycle[i].push_back(to[cycle[i].back()]);
    }

    int q;
    cin >> q;
    while(--q >= 0){
        vector<int> b(n), m(n);
        bool ng = false;
        for(int i=0; i<n; ++i){
            int x;
            cin >> x;
            -- x;

            auto it = find(cycle[x].begin(), cycle[x].end(), i);
            if(it == cycle[x].end()){
                ng = true;
            }
            else{
                b[x] = it - cycle[x].begin();
                m[x] = cycle[x].size();
            }
        }

        if(ng){
            cout << -1 << endl;
        }
        else{
            auto ans = ChineseRemainderTheorem(vector<int>(n, 1), b, m);
            if(ans.first == 0)
                cout << ans.second << endl;
            else
                cout << ans.first << endl;
        }
    }

    return 0;
}
0