結果

問題 No.590 Replacement
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-11-04 00:03:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,533 bytes
コンパイル時間 1,493 ms
コンパイル使用メモリ 105,228 KB
実行使用メモリ 18,052 KB
最終ジャッジ日時 2024-11-23 15:23:18
合計ジャッジ時間 69,135 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,240 KB
testcase_01 AC 2 ms
10,624 KB
testcase_02 AC 1 ms
10,624 KB
testcase_03 AC 2 ms
12,412 KB
testcase_04 AC 2 ms
10,624 KB
testcase_05 WA -
testcase_06 AC 3 ms
10,624 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 WA -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 AC 2 ms
13,600 KB
testcase_34 AC 2 ms
10,624 KB
testcase_35 AC 2 ms
13,600 KB
testcase_36 TLE -
testcase_37 TLE -
testcase_38 AC 585 ms
11,848 KB
testcase_39 AC 596 ms
11,848 KB
testcase_40 AC 623 ms
11,532 KB
testcase_41 AC 608 ms
11,536 KB
testcase_42 AC 591 ms
10,808 KB
testcase_43 AC 582 ms
9,636 KB
testcase_44 AC 641 ms
18,052 KB
testcase_45 TLE -
testcase_46 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

const lint MOD = 1000000007;
const bool DEBUG = false;


int gcd(int x, int y) {
  while (y != 0) {
    int remainder = x % y;
    x = y;
    y = remainder;
  }
  return x;
}

vector<int> inverse(const vector<int> &permutation) {
  int n = permutation.size();
  vector<int> result(n);
  for (int i = 0; i < n; ++i) {
    result[permutation[i]] = i;
  }
  return result;
}

void cycles(const vector<int> &permutation, vector<int> &cycle_id, vector<int> &period, vector<int> &order) {
  int n = permutation.size();
  cycle_id = vector<int>(n, -1);
  order = vector<int>(n);
  vector<int> periods;
  int count = 0;
  for (int i = 0; i < n; ++i) {
    if (cycle_id[i] >= 0) {
      continue;
    }
    cycle_id[i] = count;
    order[i] = 0;
    int p = 1;
    int current = permutation[i];
    while (current != i) {
      cycle_id[current] = count;
      order[current] = p;
      current = permutation[current];
      p++;
    }
    periods.push_back(p);
    count++;
  }
  period = periods;
}


lint crt(int x, int y, int ma, int mb) {
  for (int i = 0; i < ma; ++i) {
    lint value = (lint) y + i * (lint) mb;
    if (value % ma == x) {
      return value;
    }
  }
  assert (false);
}


lint doit(const vector<pii> &data, int ape, int bpe, int p_gcd) {
  if (data.empty()) {
    return 0;
  }
  if (DEBUG) {
    cerr << "doit:" << ape << " " << bpe << endl;
    for (auto v: data) {
      cerr << v.first << " " << v.second << endl;
    }
  }
  lint prod = (lint) ape * (lint) bpe / p_gcd;
  vector<lint> tmp;
  for (int i = 0; i < (int) data.size(); ++i) {
    pii d = data[i];
    int x = d.first;
    int y = d.second;
    int xr = x % p_gcd;
    int yr = y % p_gcd;
    lint value = crt(x - xr, y - yr, ape, bpe);
    value += xr;
    tmp.push_back(value);
  }
  sort(tmp.begin(), tmp.end());
  tmp.push_back(tmp[0] + prod);
  if (DEBUG) {
    cerr << "tmp:";
    for (auto v: tmp) {
      cerr << " " << v;
    }
    cerr << endl;
  }
  lint total = 0;
  for (int i = 0; i < tmp.size() - 1; ++i) {
    lint diff = tmp[i + 1] - tmp[i];
    total += diff * (diff - 1) / 2;
    total %= MOD;
  }
  if (DEBUG) {
    cerr << "return: " << total << endl;
  }
  return total;
}


int main(void) {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
  }
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
    b[i]--;
  }
  vector<int> ainv = inverse(a), binv = inverse(b);
  vector<int> acycle, aperiod, aorder;
  vector<int> bcycle, bperiod, border;
  cycles(ainv, acycle, aperiod, aorder);
  cycles(binv, bcycle, bperiod, border);
  if (1) {
    cerr << "acycle: ";
    for (int i = 0; i < n; ++i) {
      cerr << " " << acycle[i];
    }
    cerr << endl;
    cerr << "bcycle: ";
    for (int i = 0; i < n; ++i) {
      cerr << " " << bcycle[i];
    }
    cerr << endl;
  }
  map<pii, vector<int> > data;
  for (int i = 0; i < n; ++i) {
    pii now(acycle[i], bcycle[i]);
    data[now].push_back(i);
  }
  if (DEBUG) {
    for (auto value: data) {
      cerr << "data ";
      cerr << value.first.first << " " << value.first.second << ":";
      for (auto p: value.second) {
	cerr << " " << p;
      }
      cerr << endl;
    }
  }
  lint total = 0;
  for (map<pii, vector<int> >::iterator it = data.begin(); it != data.end(); ++it) {
    pii cycles = it->first;
    vector<int> indices = it->second;
    int acy = cycles.first;
    int bcy = cycles.second;
    int p_gcd = gcd(aperiod[acy], bperiod[bcy]);
    if (DEBUG) {
      cerr << "acy, bcy = " << acy << " " << bcy << ", pgcd = " << p_gcd << endl;
    }
    vector<vector<pii> > data(p_gcd);
    for (int i = 0; i < (int) indices.size(); ++i) {
      int index = indices[i];
      int aord = aorder[index];
      int bord = border[index];
      int diff = (aord - bord) % p_gcd;
      if (diff < 0) {
	diff += p_gcd;
      }
      data[diff].push_back(pii(aord, bord));
    }
    for (int i = 0; i < p_gcd; ++i) {
      total += doit(data[i], aperiod[acy], bperiod[bcy], p_gcd);
      total %= MOD;
    }
  }
#if 0
  for (int i = 0; i < n; ++i) {
    // (i, i) no gyaku
    lint count = 0;
    int ai = i;
    int bi = i;
    while (true) {
      if (count > 0 && ai == bi) {
	break;
      }
      ai = ainv[ai];
      bi = binv[bi];
      count++;
    }
    total = (total + count * (count - 1) / 2) % MOD;
    
  }
#endif
  cout << total << endl;
}
0