結果

問題 No.2428 Returning Shuffle
ユーザー laneguelanegue
提出日時 2023-08-18 22:28:15
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 1,783 bytes
コンパイル時間 2,455 ms
コンパイル使用メモリ 161,604 KB
実行使用メモリ 28,156 KB
最終ジャッジ日時 2023-08-18 22:28:27
合計ジャッジ時間 6,974 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 179 ms
28,156 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;
const ulong MOD = 998244353;
ulong[][] prime_division(ulong n){
  ulong[][] result;
  ulong p = 2;
  while(p <= n){
    if(n % p){
      p += 1 + (p & 1);
      continue;
    }
    result ~= [p, 0];
    while(n % p == 0){
      result[$ - 1][1] += 1;
      n /= p;
    }
  }
  return result;
}

ulong[][] pd_lcm(ulong[][] a, ulong[][] b){
  ulong[][] result;
  auto i = 0;
  auto j = 0;
  while(true){
    if(i >= a.length){
      for(; j < b.length; j++){
        result ~= b[j].dup;
      }
      break;
    }
    if(j >= b.length){
      for(; i < a.length; i++){
        result ~= a[i].dup;
      }
      break;
    }
    if(a[i][0] <= b[j][0]){
      result ~= a[i].dup;
      if(a[i][0] == b[j][0]){
        if(a[i][1] < b[j][1]){
          result[$ - 1][1] = b[j][1];
        }
        j++;
      }
      i++;
    }else{
      result ~= b[j].dup;
      j++;
    }
  }
  return result;
}

ulong pd_long(ulong[][] a){
  ulong result = 1;
  foreach(x; a){
    result *= x[0].powmod(x[1], MOD);
    result %= MOD;
  }
  return result;
}

void main(){
  auto input = readln.chomp.split.to!(int[]);
  int n = input[0];
  int m = input[1];
  auto s = new int[n];
  for(auto i = 0; i < n; i++){
    s[i] = i;
  }
  for(auto i = 0; i < m; i++){
    input = readln.chomp.split.to!(int[]);
    int prev = s[input[$ - 1] - 1];
    for(auto j = 1; j < input.length; j++){
      auto t = s[input[j] - 1];
      s[input[j] - 1] = prev;
      prev = t;
    }
  }
  auto result = prime_division(1);
  auto closed = new bool[n];
  for(auto i = 0; i < n; i++){
    if(closed[i]) continue;
    auto j = i;
    ulong k = 0L;
    while(!closed[j]){
      closed[j] = true;
      j = s[j];
      k++;
    }
    result = result.pd_lcm(prime_division(k));
  }
  writeln(result.pd_long);
}
0