結果

問題 No.2428 Returning Shuffle
ユーザー lanegue
提出日時 2023-08-18 22:54:00
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 2,026 bytes
コンパイル時間 5,790 ms
コンパイル使用メモリ 175,088 KB
実行使用メモリ 59,532 KB
最終ジャッジ日時 2024-11-28 09:16:11
合計ジャッジ時間 21,373 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;
const ulong MOD = 998244353;
const ulong N = 10 ^^ 6;
ulong[] primes;
void init_primes(){
  primes ~= 2;
  for(ulong p = 3; p < N; p += 2){
    foreach(prime; primes){
      if(p % prime == 0) break;
      if(prime ^^ 2 > p){
        primes ~= p;
        break;
      }
    }
  }
}

ulong[][] prime_division(ulong n){
  ulong[][] result;
  foreach(p; primes){
    if(p > n) break;
    if(n % p) 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;
    }
  }
  init_primes;
  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