Codechef - Starters 174 - MININV7
chefに出た。P5が綺麗な問題だった。
概要
部分列がちょうど M 種類である 01 列のうち、辞書順が大きい方から N 番目である列の転倒数を求めよ。
N,M <= 1e12
100ケース
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
解法
部分列の個数を観察。
$ dp_c[i] = i 文字目まで見て、次の文字が c であるような部分列の個数
を考えると、$ x = dp_0[i], y = dp_1[i] として、
初期化：x=1, y=1
遷移：x+=y か y+=x
答え：x+y-2
で、これは逆から見ると互除法になっている。
つまり、文字列の個数は $ \phi(M+2)である。
文字列も後ろから見ることにすると、x の大小が辞書順の大小に対応している。
文字列の長さはとても長くなりうるが、転倒数ならすぐ求まる。
その他
P2：デカい時の処理でややこしいことをしてしまい、失敗
P4：楽な方法の正当性を疑ってしまい、大変なことに
下手でした。どれくらい考察を詰めるかの塩梅がむずかしい。