2021年10月12日 日記

今日は1,100円、体重は84.8kg、問題数は1問だった。

ABC222 の G を解いた。まさか x^y≡1(mod K) の形にするなんて思いもしなかった。T <= 200 という制約を利用して前計算量 O(K) クエリ計算量 O(1) で求めるとか、ダブリングを利用すれば良さそうとか、グラフの遷移に言い換えればできるかもとか色々考えたけれど、そのどれもが間違いだった。

この問題を解くためには、x^y≡1(mod K) の他にも、基本的な mod 上の式変形の方法、オイラーの定理やオイラー関数、位数はオイラー関数の結果の約数であることなど、様々な知識が求められる。結構大変。

以下は二項係数を求めるコード。すぐに使える場所に残しておきたい。

binom[0][0] = 1;
for (int i = 1; i <= N; i++) {
  binom[i][0] = 1;
  binom[i][i] = 1;
  for (int j = 0; j < i - 1; j++) {
    binom[i][j + 1] = binom[i - 1][j] + binom[i - 1][j + 1];
  }
}