ABC422G - Balls and Boxes

ARCにも完全に同じタイトルの問題があるので紛らわしい。

問題概要

区別可能な $ 3 $ つの箱にボールを $ N $ 個入れるとき、ボールの個数がそれぞれ $ A $ の倍数、$ B $ の倍数、$ C $ の倍数になるような方法の個数を求めよ $ ( \operatorname{mod} 998244353 ) $ 。
ボール同士が $ ( 1 ) $ 区別できないとき、$ ( 2 ) $ 区別できるとき、それぞれ答えよ。

https://atcoder.jp/contests/abc422/tasks/abc422_g

考えたこと

$ N $ 以下の $ A $ の倍数を降順に見ていく。$ B $ の倍数と $ C $ の倍数に割り当てるべき残りのボールの個数 $ h $ は、非負整数 $ k $ を用いて、

$$ h = N - k A \notag $$

と表せる。また、これを非負整数 $ i , \, j $ を用いて、

$$ h = i B + j C \notag $$

と表したい。$ B , \, C $ が互いに素であるなら、

$$ i \equiv \frac { h } { B } \pmod { C } \notag $$

より、最小の $ i $ を求めることができる（互いに素でないなら、両辺を $ \gcd ( B , \, C ) $ で割ってから適用する）。$ B $ の倍数への割り当ては $ \operatorname{lcm} ( B , \, C ) $ 個ずつ増やすことができるから、単純な割り算で $ ( 1 ) $ は求められる。

$ ( 2 ) $ は、各 $ k $ に対して、

$$ \binom { N } { k A } \cdot \sum _ { t = 0 } \binom { N - k A } { i B + t \cdot \operatorname{lcm} ( B , \, C ) } \notag $$

を求めて、その総和が答えになる。

$ \operatorname{lcm} ( B , \, C ) \geq \sqrt { N } $ のときは $ t \leq \sqrt { N } $ であるから、愚直に計算すればよい。

$ \operatorname{lcm} ( B , \, C ) < \sqrt { N } $ のとき、愚直計算だと時間計算量が厳しいので少し工夫する。「 $ p $ 個のボールから $ q $ 個選ぶ方法のうち、$ q \equiv i B \pmod { \operatorname{lcm} ( B , \, C ) } $ であるようなものの総和を求める」と言い換えると、$ q $ の状態は $ \operatorname{lcm} ( B , \, C ) $ 個に限られるので DP に帰着できる。ボールを $ 1 $ 個追加するときに $ B $ の倍数に { 割り当てる、割り当てない } の $ 2 $ 通りしかないため、ボール $ 1 $ 個あたり $ O ( \sqrt { N } ) $ 回の計算で遷移できる。

提出コード

定数倍の軽い平方分割なので fastest が取れる。ほげ〜。

atcoder.jp

AtCoder 環境構築 (Linux, pyenv)

[2026/01/19 追記] 仮想環境の設定方法を Python 標準の venv から pyenv に変更したことに伴って、記事内容を大幅に変更しました。

Python 3.12 以降は pip コマンド実行に仮想環境が推奨されるらしい。

Windows ユーザーは以前の記事も参考にしてほしい。

environment

• CachyOS (Arch Linux)
• GNOME
• Visual Studio Code
• atcoder-tools
• C++ (GCC)

以下、Linux のディストリビューションやデスクトップ環境によって文法等の表記揺れがあるので注意。

install Visual Studio Code

AUR の導入まで終わっているものとする。

オープンソース版があるようだが、公式版のほうが色々と良いらしい。

> yay -S visual-studio-code-bin

extensions

• Japanese Language Pack for Visual Studio Code
• C/C++
• Python
• Bracket Lens (optional)

open folder

Visual Studio Code でワークスペース（~/programming/competitive とする）を開く。

.vscode フォルダ内の json ファイルを書き換えていく。それぞれファイルが存在しない場合は新規で作成すること。以下、重要な部分だけ抜き出して記述してある。

// c_cpp_properties.json

{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**",
                "/usr/include/**"
            ],
            "compilerPath": "/usr/bin/gcc"
        }
    ],
}

// settings.json

{
  "workspaceKeybindings.competitive.enabled": true,
  "C_Cpp.default.cppStandard": "c++20",
  "C_Cpp.default.intelliSenseMode": "gcc-x64",
}

"workspaceKeybindings.competitive.enabled" はキーボードショートカット用の環境変数で、命名は何でも良い。

install pip, pyenv, pyenv-virtualenv

> cd ~
> yay -S python-pip pyenv pyenv-virtualenv
> pyenv init

各々のデスクトップ環境に合わせた初期設定のガイダンスが表示されるので、その通りにコマンドを打ったり該当ファイルに追記したりしていく。終わったらシェルを再起動すれば済むらしいが、不安だったので一度ログアウトして再度ログインした。

install python for virtualenv

> pyenv install <python_version>

仮想環境用の Python のバージョンを pyenv にインストールする。system とは異なるバージョンをインストールすることで、仮想環境の設定ができているか確認しやすい（下記参照）。

create virtualenv

> cd ~/programming/competitive
> pyenv local <python_version>
> pyenv virtualenv <python_version> competitive_venv
> pyenv version
> python --version

下 2 行のコマンド結果で Python のバージョンが一致していれば無事に設定完了。そうでない場合（特に python --version の結果が system のバージョンと一致している場合）、pyenv の初期設定がうまくいってない可能性が高い。

install atcoder-tools

> cd ~/programming/competitive
> pip install atcoder-tools
> pip install markupsafe==2.0.1

インストールが終わったら ~/.atcodertools.toml を作成する。

# .atcodertools.toml

[codestyle]
indent_type='space' # 'tab' or 'space'
indent_width=2
template_file='~/programming/competitive/template.cpp'
workspace_dir='~/programming/competitive/atcoder-workspace/'
lang='cpp' # Check README.md for the supported languages.
# code_generator_toml="~/universal_code_generator.toml"
[postprocess]
exec_on_each_problem_dir='basename `pwd` >> ../.atcodertools_directories.txt'
exec_on_contest_dir='data=(`tac .atcodertools_directories.txt`); if [ ${#data[@]} -le 10 ]; then for dir in ${data[@]}; do code -g ${dir}/main.cpp:71:3; done; fi'
[compiler]
compile_command='g++ main.cpp -o main -std=gnu++20 -O2 -Wall -Wextra'
compile_only_when_diff_detected=false
[tester]
compile_before_testing=true
compile_only_when_diff_detected=false
timeout_adjustment=1.2
[etc]
download_without_login=false
parallel_download=false
save_no_session_cache=false
skip_existing_problems=true
in_example_format="in_{}.txt"
out_example_format="out_{}.txt"

コード生成テンプレートファイルがない場合は別途作成する。
（参考: GitHub - kyuridenamida/atcoder-tools: Convenient modules & tools for AtCoder users, written in Python 3.9）

exec_on_contest_dir 内の main.cpp:71:3 はテンプレートファイルに合わせて行数と列番号を変更すること。

set up keybindings

.vscode/tasks.json に追記する。

// tasks.json

{
  "tasks": [
    {
      "label": "atcoder-tools gen",
      "type": "shell",
      "command": "atcoder-tools gen ${input:contest_id}",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": false,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": true
      },
      "options": {
        "cwd": "${workspaceFolder}"
      }
    },
    {
      "label": "atcoder-tools test",
      "type": "shell",
      "command": "atcoder-tools",
      "args": [
        "test",
        "--compile-command",
        "'g++ main.cpp -D_DEBUG -o main -std=gnu++20 -O2 -Wall -Wextra'"
      ],
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    },
    {
      "label": "atcoder-tools submit",
      "type": "shell",
      "command": "atcoder-tools submit -u",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    }
  ],
  "inputs": [
    {
      "id": "contest_id",
      "type": "promptString",
      "description": "enter the AtCoder contest_id",
      "default": ""
    }
  ]
}

続いて、左下の歯車アイコン、あるいは Ctrl+K Ctrl+S から [キーボード ショートカット] を開き、右上のアイコンから [キーボード ショートカットを開く (JSON)] を探し出して keybindings.json を開く。

// keybindings.json

[
  {
    "key": "Ctrl+F1",
    "command": "workbench.action.tasks.runTask",
    "when": "config.workspaceKeybindings.competitive.enabled",
    "args": "atcoder-tools gen"
  },
  {
    "key": "F5",
    "command": "workbench.action.tasks.runTask",
    "when": "config.workspaceKeybindings.competitive.enabled && (editorLangId == cpp || terminalFocus)",
    "args": "atcoder-tools test"
  },
  {
    "key": "F9",
    "command": "workbench.action.tasks.runTask",
    "when": "config.workspaceKeybindings.competitive.enabled && (editorLangId == cpp || terminalFocus)",
    "args": "atcoder-tools submit"
  }
]

login with atcoder-tools

ログイン時の ReCAPTCHA に atcoder-tools が対応していないため、ブラウザ等の Cookie 値をコピペする。atcoder-tools 側から一度もログインしていない場合は /.local/share/atcoder-tools/cookie.txt を作成する。

#LWP-Cookies-2.0
Set-Cookie3: REVEL_SESSION="" domain="atcoder.jp"; path_spec; secure; expires="2026-04-30 01:05:00Z"; HttpOnly=None; version=0

REVEL_SESSION の二重引用符にコピペする。
（参考: 主要ブラウザCookieの確認方法まとめ #Chrome - Qiita）

セッションの有効期限は半年後くらいに書き換える。 100 年後とかでも良いらしい。

これで一通り動くはず。

winning run...

後書きのようなもの。

Windows 11 から半ば離脱するつもりで SSD を買い足してデュアルブート環境を構築した。atcoder-tools の導入もすぐに終わると思っていたが、仮想環境周りで丸 2 日ほど消費した。。。

atcoder-tools gen 実行後のファイルオープンが爆速になったのはとても良い。

[2026/01/19 追記] Python 標準の venv だと system 側での Python のバージョンアップにより atcoder-tools が動かなくなったようで、急遽 pyenv に変更した。tasks.json 内の "reveal": "silent" が機能するようになったのが地味に嬉しい。

AGC019E - Shuffle and Swap

組み合わせ論のみで通せる。

問題概要

atcoder.jp

考えたこと

丁寧に考察していくと、$ A $ に存在する特定の $ 0 $ を特定の位置に移動させることで $ A = B $ を実現させる、と言い換えられる。

$ 0 $ を移動させていく過程において、最終位置に直接移動させるパターンと、$ A _ v = B _ v = 1 $ であるような位置 $ v $ を経由しながら移動させるパターンが存在している。

（ここまで公式解説とほぼ同じ）

1. 移動させたい全ての $ 0 $ について、移動元と移動先（＝最終位置）のペアを作って並べる。これを $ C $ とする。

2. 経由候補となる位置を $ 1 $ つ選んで $ C $ に挿入する。このとき、挿入済の経由位置よりも左に挿入しなくてはならない。
   挿入後、右側に存在するペアから $ 1 $ つ選んでペアを付け替える。
   元々 x->y のペアが存在していて v を経由したいとき、元々のペアを v->y に付け替えて、$ C $ に挿入した v を x->v のペアとして扱うことにする。その後、v->y のペアを $ C $ から削除する。
   この挿入を任意の回数繰り返す。

3. 残った経由候補について適当にペアリングして適当に $ C $ に挿入する。

これによって得られる $ C $ の個数を求めればよい。2. の立式は、挿入位置の右側に存在するペアの個数を $ i $ 、まだ選ばれていない経由候補の個数を $ r $ として、

$$ ndp[i] \xleftarrow { + } i \cdot r \cdot \sum _ { k = 0 } ^ { i } { dp[i] } \notag $$

となって、これに 3. の値を掛けたものの総和が求める値である。

計算量は $ O ( N ^ 2 ) $ であるが、定数倍がかなり軽いので全然問題ない。

提出コード

atcoder.jp

赤黒木 with 二項演算

うしさんのライブラリを改変して機能モリモリにしていたらバグったので書き直しました。

アルゴリズム概要

speakerdeck.com

↑大変参考になりました。

各ライブラリのイメージ

折角なので、順序付き赤黒木と遅延評価赤黒木も作りました（後者はうしさんも作ってましたが）。

• 通常版　：任意に挿入・削除できるセグメント木
• 順序付き：二項演算できる std::multiset
• 遅延評価：任意に挿入・削除できる遅延評価セグメント木

という感覚です。

それぞれ共通部分が多いのでクラス継承を考えましたが、メリットが大してない上に using 宣言だらけになってしまったのでやめました。

実装方針

挿入・削除操作は上記スライドの内容をほぼそのまま書き起こしました。

葉以外のノードにもデータを載せています。

注意点

削除したいノードが葉でない場合、（列として見たときに）すぐ隣の葉ノードと値を swap してからその葉ノードを削除する、という挙動になっています。
このため、削除操作を行う前に取得したノードポインタを引数に用いると、想定した挙動にならない場合があります（最悪壊れます）。

その他の細かな注意点はコード内にコメントアウトしてあります。

実装

vector_pool.hpp

red_black_tree.hpp （通常版）

ordered_red_black_tree.hpp （順序付き）

lazy_red_black_tree.hpp （遅延評価）

検証

挿入・削除操作はランダムケースをそれなりに回して目視で確認したので合っているはずです。

その他の操作は未検証なのでバグっている可能性があります。自己責任でご利用ください。

ARC195 (Div.2) E - Random Tree Distance

行列演算で brain-dead に DP したい人向け。既存手法っぽさあるけど念の為。

問題概要

atcoder.jp

DP の立式

0-indexed とする。

$ P _ i < i $ より、各頂点を昇順に見ていく間に、

1. LCA
2. パスに含まれる頂点集合 $ X $
3. 頂点 $ u $
4. パスに含まれる頂点集合 $ Y $
5. 頂点 $ v $

の順に選択する。

頂点 $ i $ まで見て既に $ 2 $ 頂点以上選んでいる（＝辺重みに寄与している）ときの $ P _ 1 $ から $ P _ i $ までの選び方を $ f [ i ] $ 、辺重みの総和を $ w [ i ] $ とする。
この定義より、$ f [ 0 ] = w [ 0 ] = 0 $ である。また、求める値は $ w [ v ] \cdot {} _ { n - 1 } \mathrm { P } _ { ( n - 1 ) - v } $ である。

1. LCA を選ぶ

LCA を選ぶだけでは辺重みに寄与しないため、LCA はまだ選んでいないと見做して、初めて LCA 以外の頂点を選ぶときに同時に LCA も選ぶこととする。

2. パスに含まれる頂点集合 $ X $ を選ぶ

• $ f [ i ] \xleftarrow { + } i ! $
• $ w [ i ] \xleftarrow { + } A [ i ] \cdot i ! $

初めて LCA 以外の頂点を選ぶ場合、$ P _ 1 $ から $ P _ i $ までの選び方には追加の制約がない。
特に、LCA はまだ選んでいないことになっているため、LCA としての $ P _ i $ についても任意の頂点を選ぶことができる。

LCA 以外の頂点を選んでいる場合はさらに、各頂点 $ i $ に対して、$ i \in X $ とするかどうかで場合分けをする。

• $ f [ i ] \xleftarrow { + } 2 \cdot f [ i - 1 ] $
• $ w [ i ] \xleftarrow { + } 2 \cdot ( w [ i - 1 ] + A [ i ] \cdot f [ i - 1 ] ) $

$ i \in X $ である場合、$ 2 $ つあるパスのうちどちらか片方の葉を $ i $ の親とするため、$ P _ i $ の選び方は $ 2 $ 通りある。

• $ f [ i ] \xleftarrow { + } i \cdot f [ i - 1 ] $
• $ w [ i ] \xleftarrow { + } i \cdot w [ i - 1 ] $

$ i \notin X $ である場合、$ P _ i $ の選び方には制約がない。

3. 頂点 $ u $ を選ぶ

上記 2. から $ i \notin X $ である場合を除外する。
また、$ u $ を LCA として選ぶことも可能である（ただし辺重みには寄与しない）。

4. パスに含まれる頂点集合 $ Y $ を選ぶ

• $ f [ i ] \xleftarrow { + } ( i - 1 ) ! $
• $ w [ i ] \xleftarrow { + } A [ i ] \cdot ( i - 1 ) ! $

初めて LCA 以外の頂点を選ぶ場合、$ P _ 1 $ から $ P _ { i - 1 } $ までの選び方には追加の制約がない。
一方で、LCA の候補は $ u $ のみであるため、 $ P _ i = u $ が確定している。

LCA 以外の頂点を選んでいる場合はさらに、各頂点 $ i $ に対して、$ i \in Y $ とするかどうかで場合分けをする。

• $ f [ i ] \xleftarrow { + } f [ i - 1 ] $
• $ w [ i ] \xleftarrow { + } w [ i - 1 ] + A [ i ] \cdot f [ i - 1 ] $

$ i \in Y $ である場合、$ 2 $ つあるパスのうち葉を $ u $ とする方は選ぶことができないため、$ P _ i $ の選び方は $ 1 $ 通りのみである。

• $ f [ i ] \xleftarrow { + } i \cdot f [ i - 1 ] $
• $ w [ i ] \xleftarrow { + } i \cdot w [ i - 1 ] $

$ i \notin Y $ である場合、$ P _ i $ の選び方には制約がない。

5. 頂点 $ v $ を選ぶ

上記 4. から $ i \notin Y $ である場合を除外する。

行列演算化

上記 2. から 5. までを $ 3 \times 3 $ 行列 $ M $ を用いて、

$$ \Bigl( \begin{array}{ccc} w [ i ] & f [ i ] & i ! \\ \end{array} \Bigr) = \Bigl( \begin{array}{ccc} w [ i - 1 ] & f [ i - 1 ] & ( i - 1 ) ! \\ \end{array} \Bigr) \left( \begin{array}{ccc} □ & □ & □ \\ □ & □ & □ \\ □ & □ & □ \\ \end{array} \right) \notag $$

の形に持ち込む。

2. パスに含まれる頂点集合 $ X $ を選ぶ

$$ M = \left( \begin{array}{ccc} i + 2 & 0 & 0 \\ 2 \cdot A [ i ] & i + 2 & 0 \\ i \cdot A [ i ] & i & i \\ \end{array} \right) \notag $$

3. 頂点 $ u $ を選ぶ

$$ M = \left( \begin{array}{ccc} 2 & 0 & 0 \\ 2 \cdot A [ u ] & 2 & 0 \\ i \cdot A [ u ] & u & u \\ \end{array} \right) \notag $$

4. パスに含まれる頂点集合 $ Y $ を選ぶ

$$ M = \left( \begin{array}{ccc} i + 1 & 0 & 0 \\ A [ i ] & i + 1 & 0 \\ A [ i ] & 1 & i \\ \end{array} \right) \notag $$

5. 頂点 $ v $ を選ぶ

$$ M = \left( \begin{array}{ccc} 1 & 0 & 0 \\ A [ v ] & 1 & 0 \\ A [ v ] & 1 & v \\ \end{array} \right) \notag $$

セグメント木と固定長行列演算

上記 2. および 4. における行列乗算を $ O ( \log N ) $ 回に抑えるために、それぞれセグメント木を用意して行列演算を載せる。

あとは各クエリを処理するだけに思えるが、手元環境で最悪ケースの簡易的な TLE チェックをしてみると約 4500 ms であった。
原因は（ほぼ確実に）行列演算ライブラリが vector ベースで実装されていることにあり、特に行列の乗算を行う際に毎回 vector 用のメモリを（かなり余分に）確保してしまうために定数倍が悪くなっている（と思われる）。

そこで、vector ベースではなく array ベースの固定長行列演算ライブラリを用意する。
このライブラリに置き換えて TLE チェックをしてみると約 420 ms となって、約 10 倍高速に処理できる。

使用方法は通常の行列演算ライブラリとほぼ同じだが、行列のサイズが固定されているため operator*= を定義していない点のみ注意してほしい。
実装は提出コードを参照のこと（うしさんの実装を改変しました、いつもお世話になっております）。

提出コード

atcoder.jp

デバッグ用ヘッダファイル for 競プロ

kyokkounoite.hatenablog.jp

kyokkounoite.hatenablog.jp

だいぶ前の続き。任意のテストケースを実行したときのターミナルでの見栄えを良くしつつ、簡易的な TLE チェックをするために色々と改変した。

target

• GCC
• Visual Studio Code
• atcoder-tools

goal of this article

デバッグ中に main.cpp を書き換えることなく、

1. 与えられたテストケースの実行
2. 任意のテストケースの実行
3. TLE チェック
4. コード提出

を不自由なく行えるようにする。

なお、1 と 4 は atcoder-tools をそのまま利用しているだけなので割愛。

ENABLE_MIGHT_IO

順番が前後するが、TLE チェックの方を先に説明する。

簡潔に述べると、まず enable_might_io.hpp というファイルを用意して、このファイル内で #define ENABLE_MIGHT_IO を宣言する。
それと同時に「cin の代わりに乱数を格納し、cout は実行しない」ような、入出力を代替する関数群（以下、might_io）を定義する。
次に、main.cpp において #ifndef ENABLE_MIGHT_IO 以下に「通常の入出力を行う」might_io を定義しておく。
入力時に cin を用いるか might_io を用いるかの判断はコーディング時に行い、コンパイル時に -include [[folder_path]]/enable_might_io.hpp コマンドを追加する。

こうすると、例えば「長さ N の数列 A」に対して「N は入力して A は乱数で埋める」ということが可能になり、最悪ケース（またはそれに近しいケース）を試すことができる。

具体的なコードは最後に記してある。

ENABLE_ARBITRARY_TEST

これまでは「入力した文字と出力された文字の色が同じ」というターミナル環境だったため、連続して実験すると入出力の判別がしにくく若干不便だった。

#ifdef ENABLE_ARBITRARY_TEST
inline void prompt_bkgndclr(const char* cmd) { cout << cmd; }
#else
inline void prompt_bkgndclr(const char*) {}
#endif

template<typename... Args>
inline void might_out(const Args&... args) {
  prompt_bkgndclr("\e[45m");
  // cout
  prompt_bkgndclr("\e[49m");
  cout << '\n';
}

のようにすると、ENABLE_ARBITRARY_TEST が define されているときのみ出力の背景色が紫色になる。

コンパイルコマンドに -DENABLE_ARBITRARY_TEST を含めると main.cpp を汚染せずに define できる。

winning run...

御多分に洩れず自己責任の範疇において自由に複製・利用・改変してもらって構わない。

main.cpp

might_in_extra() は TLE チェック時のみ実行される乱数埋め関数である。

#include <bits/stdc++.h>
using namespace std;

#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
using ll = int64_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
template<typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr int MOD = 998244353;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
char interval[2] = {' ', '\n'};

template<typename T, typename... Args> auto make_vector(T x, int arg, Args... args) { if constexpr(sizeof...(args) == 0) return vector<T>(arg, x); else return vector(arg, make_vector<T>(x, args...)); }

template<typename T> struct is_plural : false_type{};
template<typename T1, typename T2> struct is_plural<pair<T1, T2>> : true_type{};
template<typename T> struct is_plural<complex<T>> : true_type{};
template<typename T> struct is_plural<vector<T>> : true_type{};
template<> struct is_plural<string> : true_type{};

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) { return is >> p.first >> p.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << ' ' << p.second; }
template<typename T> istream& operator>>(istream& is, complex<T>& x) { T a, b; is >> a >> b; x = complex<T>(a, b); return is; }
template<typename T> ostream& operator<<(ostream& os, const complex<T>& x) { return os << x.real() << ' ' << x.imag(); }
template<typename T> istream& operator>>(istream& is, vector<T>& vec) { for(auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { if(vec.empty()) return os; os << vec.front(); for(auto itr = ++vec.begin(); itr != vec.end(); ++itr) os << interval[is_plural<T>()] << *itr; return os; }

inline bool CoutYN(bool a, string yes = "Yes", string no = "No") { cout << (a ? yes : no) << '\n'; return a; }

template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); }

#ifdef _DEBUG
void dbg() { cerr << '\n'; }
template<typename T, typename... Args> void dbg(const T& x, const Args&... args) { cerr << '\n' << x; dbg(args...); }
template<typename... Args> inline void debugger(int line, const char* str, const Args&... args) { cerr << "\e[96m" << line << " [" << str << "]:\e[39m"; dbg(args...); };
#else
template<typename... Args> inline void debugger(int, const char*, const Args&...) {};
#endif
#define debug(...) debugger(__LINE__, #__VA_ARGS__, __VA_ARGS__)

#ifdef ENABLE_ARBITRARY_TEST
inline void prompt_bkgndclr(const char* cmd) { cout << cmd; }
#else
inline void prompt_bkgndclr(const char*) {}
#endif

#ifndef ENABLE_MIGHT_IO
inline void might_set_range(int64_t, int64_t) {}
inline void might_in() {}
template<typename T, typename... Args> inline void might_in(T& x, Args&... args) { cin >> x; might_in(args...); }
template<typename T, typename... Args> inline void might_in_extra(T&, Args&...) {}
inline void might_out_impl() {}
template<typename T, typename... Args> inline void might_out_impl(const T& x, const Args&... args) { cout << x; might_out_impl(args...); }
template<typename... Args> inline void might_out(const Args&... args) { prompt_bkgndclr("\e[45m"); might_out_impl(args...); prompt_bkgndclr("\e[49m"); cout << '\n'; }
inline void might_finished() {}
#endif


/* -------- <insert libraries below> -------- */


/* -------- <templates end> -------- */


void solve() {
  
}


/* -------- <programs end> -------- */


signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  solve();
  might_finished();
  return 0;
}

enable_might_io.hpp

実行時間（正確には、最後に random_in() が呼び出されてからプログラムが終了するまでの時間）も出力される。

各 Modint 構造体に対して struct is_modint<Modint> : std::true_type{}; を宣言しておかないと、 random_in() の引数に Modint を指定した場合にコンパイルエラーが発生するようにしている点に注意。

#pragma once
#include <bits/stdc++.h>

#define ENABLE_MIGHT_IO

template<typename> struct is_modint : std::false_type{};

namespace EnableMightIO {
  inline auto get_now() {
    return std::chrono::steady_clock::now();
  }

  struct RandomNumberGeneratorForDebug {
    std::mt19937_64 mt;
    std::uniform_int_distribution<int64_t> dist;

    RandomNumberGeneratorForDebug() : mt(get_now().time_since_epoch().count()), dist(0, 0) {}

    int64_t operator()() {
      return dist(mt);
    }

    void set(int64_t low, int64_t high) {
      assert(low <= high);
      dist.param(decltype(dist)::param_type(low, high));
    }
  };

  RandomNumberGeneratorForDebug rng;
  auto last_input_time = get_now();

  template<typename T> inline void random_in_impl(T& x) {
    static_assert(std::is_arithmetic_v<T> || is_modint<T>());
    x = rng();
  }

  template<typename T1, typename T2> inline void random_in_impl(std::pair<T1, T2>& x) {
    random_in_impl(x.first), random_in_impl(x.second);
  }

  template<typename T> inline void random_in_impl(std::complex<T>& x) {
    T a, b;
    random_in_impl(a), random_in_impl(b);
    x.real(a), x.imag(b);
  }

  template<typename T> inline void random_in_impl(std::vector<T>& x) {
    for(auto& v : x) random_in_impl(v);
  }

  template<> inline void random_in_impl(std::string& x) {
    for(auto& v : x) random_in_impl(v);
  }

  inline void random_in() {
    last_input_time = get_now();
  }

  template<typename T, typename... Args> inline void random_in(T& x, Args&... args) {
    random_in_impl(x);
    random_in(args...);
  }
}

inline void might_set_range(int64_t low, int64_t high) {
  EnableMightIO::rng.set(low, high);
}

template<typename T, typename... Args> inline void might_in(T& x, Args&... args) {
  return EnableMightIO::random_in(x, args...);
}

template<typename T, typename... Args> inline void might_in_extra(T& x, Args&... args) {
  return EnableMightIO::random_in(x, args...);
}

template<typename T, typename... Args> inline void might_out(const T&, const Args&...) {}

inline void might_finished() {
  using namespace EnableMightIO;
  using namespace std::chrono;
  std::cerr << "\e[96mFINISHED\e[39m " << duration_cast<milliseconds>(get_now() - last_input_time).count() << " ms\n";
}

tasks.json

使いやすいキーボードショートカットを割り当てるべし。

{
  ...
  "tasks": [
    {
      "label": "atcoder-tools test",
      "type": "shell",
      "command": "atcoder-tools",
      "args": [
        "test",
        "--compile-command",
        "'g++ main.cpp -D_DEBUG -o main -std=gnu++20 -O2 -Wall -Wextra'"
      ],
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": false,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    },
    {
      "label": "atcoder-tools arbitrary test",
      "type": "shell",
      "command": "atcoder-tools",
      "args": [
        "test",
        "--compile-command",
        "'g++ main.cpp -D_DEBUG -DENABLE_ARBITRARY_TEST -o main -std=gnu++20 -O2 -Wall -Wextra'",
        "-n",
        "0",
        ";",
        "timeout",
        "--kill-after=1",
        "300",
        "./main"
      ],
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    },
    {
      "label": "atcoder-tools check TLE",
      "type": "shell",
      "command": "atcoder-tools",
      "args": [
        "test",
        "--compile-command",
        "'g++ main.cpp -D_DEBUG -o main -std=gnu++20 -O2 -Wall -Wextra -include C:/programming/competitive/enable_might_io.hpp'",
        "-n",
        "0",
        ";",
        "timeout",
        "--kill-after=1",
        "20",
        "./main"
      ],
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    },
    {
      "label": "atcoder-tools submit",
      "type": "shell",
      "command": "atcoder-tools submit -u",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    },
    {
      "label": "atcoder-tools force submit",
      "type": "shell",
      "command": "atcoder-tools submit -f -u",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    }
  ],
  ...
}

ARC191 (Div.2) C - A^n - 1

本番中に落ち着いて考察できてたら通せてたかも。

問題概要

$ \mod M $ において $ A ^ k \not\equiv 1 ( 0 < k < N ) $ かつ $ A ^ N \equiv 1 $ となるような整数の組 $ ( A , M ) $ を一つ求めよ。
$ 1 \leq N \leq 10 ^ 9 , \, 1 \leq A \leq 10 ^ { 18 } , \, 1 \leq M \leq 10 ^ { 18 } $

https://atcoder.jp/contests/arc191/tasks/arc191_c

考えたこと

カーマイケルの定理を用いて $ M $ を一つ割り出し、乱択あるいは昇順に $ A $ を走査する。

カーマイケルの定理（Wikipedia）とは、$ a $ と $ m $ が互いに素なとき、カーマイケル関数 $ \lambda ( m ) $ を用いて、

$$ a ^ { \lambda ( m ) } \equiv 1 \pmod m \notag $$

が成り立つという定理である。ここで、カーマイケル関数 $ \lambda ( m ) $ は以下のように再帰的に定義される（ $ p $ は素数）。

$$ \begin{array}{lllll} \lambda ( 2 ^ e ) = \left\{ \begin{align} & 1 & ( e = 1 ) \notag \\ & 2 & ( e = 2 ) \notag \\ & 2 ^ { e - 2 } & ( e \geq 3 ) \notag \end{align} \right. \\ \\ \lambda ( p ^ e ) = p ^ { e - 1 } ( p - 1 ) \qquad ( p \neq 2 ) \notag \\ \\ \lambda ( p _ 1 ^ { e _ 1 } \cdots p _ k ^ { e _ k } ) = \operatorname{lcm} \lbrace \lambda ( p _ 1 ^ { e _ 1 } ) , \cdots , \lambda ( p _ k ^ { e _ k } ) \rbrace \notag \end{array} $$

今回は、$ \lambda ( M ) = k N $ となるように $ M $ を定めることができればよい。具体的には、

$$ \begin{array}{lllll} \Lambda ( 2 ^ e ) = \left\{ \begin{align} & 4 & ( e = 1 ) \notag \\ & 2 ^ { e + 2 } & ( e \geq 2 ) \notag \end{align} \right. \\ \\ \Lambda ( p ^ e ) = p ^ { e + 1 } \qquad ( p \neq 2 ) \notag \\ \\ \Lambda ( p _ 1 ^ { e _ 1 } \cdots p _ k ^ { e _ k } ) = \Lambda ( p _ 1 ^ { e _ 1 } ) \cdots \Lambda ( p _ k ^ { e _ k } ) \notag \end{array} $$

を満たす関数 $ \Lambda ( n ) $ を定義し、$ M = \Lambda ( N ) $ とすればよい。$ \Lambda ( N ) \leq N ^ 2 $ より $ M \leq 10 ^ { 18 } $ を満たす。

$ A $ の走査方法に関しては特段変わったところはないので省略。「原始根」で検索すると記事があると思う。

提出コード

atcoder.jp

想定解として $ M = N ^ 2 $ が挙げられているのも納得できる。