bijective numeration（Excel 進数的なやつ）の訳を「全単射記数法」として定着させたい

　文字列を数字に対応させたいというときは良くあります。

- `aaa` -> $111$
- `aab` -> $112$

　といった感じに。

　`a~f` を用いた $16$ 進数も、このような対応付けの一種と言えます。

- `10` -> $16$
- `ff` -> $15\times16+15=255$

# いわゆる Excel 進数

　ここで、次のような数え方を考えてみましょう。

- まず、`a~z` までを使う
- それが終わったら、`aa~zz` までを使う
- それが終わったら（以下略）

　皆様にも馴染みの深い、**Excel の列** です。

　しかし、例えば、`a~z` の $26$ 文字を、$0\sim 25$ に割り当てた場合、以下のようになっておかしくなります。

- `a` -> $0$
- `aa` -> $0 \times 26+0=0$
- $25$ -> `z`
- $26$ -> `ba`

　`a` と `aa` が同じ数字になったり、`z` の次が `ba` になったりと、いろいろおかしいです。

　これは、`a` を $0$ とみなしているにも関わらず、数え方がそうなっていないために起こります。
 
　ならば、$0\sim26$ の $27$ 進数にすれば良いかというと、今度は別の問題が出てきます。便宜的に、「無」を `_` と表現します。

- $0$ 番目の文字列 -> `__`
- $1$ 番目の文字列 -> `_a`
- $26$ 番目の文字列 -> `_z`
- $27$ 番目の文字列 -> `a_`
- $28$ 番目の文字列 -> `aa`

　本来、`_z` の次は `aa` であるべきですが、`a_` になってしまいます。これでは、正しい数え上げができません。

　このような特殊な数え方をする $N$ 進数について考えていきます。

# 基本の進数の数え上げ

　まずは簡単な例として、普通の $N$ 進数から。

## 変換
 
　単純な $16$ 進数で考えると、$n$ と文字列は以下の通りシンプルに変換できます。

- $10,000$ 番目の文字列は？
　- $10,000$ を $16$ でわるとあまり $0$、よって $0$ 番目の文字である `0`（$1$ 桁目）
　- $\lfloor\frac{10000}{16}\rfloor = 625$
　- $625$ を $16$ でわるとあまり $1$、よって $1$ 番目の文字である  `1`（$2$ 桁目）
　- $\lfloor\frac{625}{16}\rfloor = 39$
　- 同様に、`7`（$3$ 桁目）
　- 同様に、`2`（$4$ 桁目）
　- よって `2710`
- `2710` は何番目の数？
  - $2\times16^3+7\times16^2+1\times16+0\times 1=10,000$

## 数え上げ表

　また、「$D$ 桁以下の文字列が何個あるか」も非常に考えやすいです。$10$ 進数を考えます。これはほぼ自明に $10^D$ です（※ `0` もカウントすることに注意してください）。

　$D$ 桁以下の文字列の個数がわかるということは、ちょうど $D$ 桁の個数も当然わかります。「ちょうど $D$ 桁になる文字列」の個数は、$10^D-10^{(D-1)}=9 \cdot 10^{(D-1)}$ です。

　表にまとめるとこんな感じです。

**$N$ 進数の数え上げ表（$10$ 進数の場合）**

|桁|範囲|個数|桁（累計）|範囲|個数|
|---|---|---|---|---|---|
|$D=0$|$[0,1)$|$1$|$D\leq0$|$[0,1)$|$1$|
|$D=1$|$[1,10)$|$9$|$D\leq1$|$[0,10)$|$10$|
|$D=2$|$[10,100)$|$90$|$D\leq2$|$[0,100)$|$100$|
|$D=3$|$[100,1000)$|$900$|$D\leq3$|$[0,1000)$|$1000$|
|$\vdots$|$\vdots$|$\vdots$|$\vdots$|$\vdots$|$\vdots$|
|$D=M$|$[10^{M-1},10^M)$|$9 \times 10^{M-1}$|$D\leq M$|$[0,10^M)$|$10^M$|

※ $D=0$ のときは、$0$ 桁の文字列であり、つまり `0` がそれにあたります。

# 特殊な進数の数え上げ

　では、Excel 進数などで使われる数え上げについて、同じようなパターンで検証しています。`AA` だとわかりづらいので、`1~9` の $9$ 種類の数を使う文字列で、Excel の列のように増えていくものとします。
 
　結論から言うと、以下のように、**1-indexed** の $9$ 進数として考えるとうまく変換できます。

- $19$ 番目の文字列は？
　- $19$ を $9$ で割るとあまり $1$、よって、$1$ 番目の文字である `1`（$1$ 桁目）
　- $(\lceil \frac{19}{9} \rceil-1) = 2$
　- $2$ を $9$ で割るとあまり $2$、よって、$2$ 番目の文字である `2`（$2$ 桁目）
- `21` はどんな数？
  - こっちは普通に $N$ 進数として考えて大丈夫です
  - $2\times9+1 = 19$

※ `1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21` より（1-indexedの） $19$ 番目の文字列です

※ 文字列の変換について、プログラム上は、各桁ごとにデクリメントした上で `0-indexed` と考える方が簡潔に実装できます（詳細は後述する実装例）

## 数え上げ表
 
　こちらは、単純な $N$ 進数とは変わって、差分の法がわかりやすいです。ちょうど $D$ 桁に含まれる文字列は `1~9` を $D$ 個あてはめるだけなので、$9^D$ です。表にまとめます。

**特殊 $N$ 進数の数え上げ表（$9$ 進数の場合）**
|桁|範囲|個数|桁（累計）|範囲|個数|
|---|---|---|---|---|---|
|$D=0$|$[1,1)$|$0$※|$D\leq0$|$[1,1)$|$0$|
|$D=1$|$[1,11)$|$9$|$D\leq1$|$[1,11)$|$9$|
|$D=2$|$[11,111)$|$81$|$D\leq2$|$[1,111)$|$90$|
|$D=3$|$[111,1111)$|$729$|$D\leq3$|$[1,1111)$|$819$|
|$\vdots$|$\vdots$|$\vdots$|$\vdots$|$\vdots$|$\vdots$|
|$D=M$|$[111\cdots,111\cdots)$|$9^M$|$D\leq M$|$[1,111\cdots)$|$\frac{9^{M+1}-1}{8}-1$|

※ $D=0$ のときは例外処理が必要です。なんか数学的に気持ち悪いので、$[1,1)$ に $1$ 個の「無」の文字列が含まれると考えれば累計の $-1$ も消えてスッキリしますが、まあ、これは捉え方の問題で、やる計算は同じです。

# 名前

　このような特殊な $N$ 進数に名前があるのかというと、当然あって、[bijective numeration](https://en.wikipedia.org/wiki/Bijective_numeration) と呼ばれているらしいです。

　bijective とは「全単射」のことであり、つまり一対一対応のことです。

　どういうことかというと、まず、普通の $N$ 進数だと、`1` も `01` も `001` も同じ数（$=1$）を示してしまいます。この点、bijective-N 進数だと、異なる文字列が同じ数を示すということがなく、一対一対応します。

　さて、この bijective-N ですが、日本語で定まった訳がないようです。一応、[参考記事 3](https://scrapbox.io/wint/%E5%85%A8%E5%8D%98%E5%B0%84%E8%A8%98%E6%95%B0%E6%B3%95)では bijective numeration に対して「全単射記数法」という訳を当てています。ほぼ直訳ですが、まあ誰が訳してもこうなりそうですし、妥当だと思います。

　という訳で、本記事では、この訳語を採用し定着させるとともに、他に「全単射 $N$ 進数」といった表記を提案したいと思います。

例）「Excel の列は、$26$ を基数とした全単射 $26$ 進数によって管理されている」

# 実装及び検証

## 数→文字列
https://atcoder.jp/contests/abc171/submissions/57825787
## 文字列→数
https://atcoder.jp/contests/abc285/submissions/57836276

# 参考記事

1. [桁数付きビットパターンの整数表現、関連する話題](https://ngtkana.hatenablog.com/entry/2024/06/27/005117)
1. [ABC285 C問題：ゼロを使わないN進法についてのメモ](https://qiita.com/HMMNRST/items/e9e68d58de3a1d1d7c85)
1. [全単射記数法](https://scrapbox.io/wint/%E5%85%A8%E5%8D%98%E5%B0%84%E8%A8%98%E6%95%B0%E6%B3%95)