(だいぶ換言した) 問題概要
関数 $f(A)$ は数列 $A=(A_0,A_1,\dots,A_{|A|-1})$ を引数に取り、未知のパラメータ $p,m $ を用いて以下の通りに定義される。
$\displaystyle f(A) = \sum^{|A|-1}_{k=0} A_k \times p^k \mod m $
以下の条件を全て満たす数列 $B$ を用いて、関数 $f(B)$ の値を $3$ 度まで尋ねることができる。
- 数列 $B$ は長さ $1$ 以上 $50$ 以下
- 数列 $B$ の全ての要素は $1$ 以上 $26$ 以下の整数
$p,m $ を特定せよ。
但し、 $p$ は $27$ 以上 $50$ 以下、 $m $ は $p+2$ 以上 $2 \times 10^9$ 以下の整数である。
↑ 後々分かることだが、これらの制約はかなり重要。
本題に入る前に、追加で $\displaystyle g(A) = \sum^{|A|-1}_{k=0} A_k \times p^k$ ( つまり、 $\rm{mod}$ を取る前の $f(A)$ ) と定義しておく。
気付きにくいが指摘されると自明な処理として、まず $f([1,1])$ を尋ねることを考える。
このとき $g([1,1]) = p+1$ であり、 $m $ が $p+2$ 以上であることから $g([1,1]) = f([1,1])$ が成り立ち $p$ を特定できる。
ここから質問を $2$ 回使って $m $ の特定に入る。天下り的だが、 $g([26,26,\dots,26])$ が $m $ に対して十分大きくなるように尋ねる。
$p \le 50$ であることから、 $g$ が $10^{13} \sim 10^{16}$ 程度となる ( long long で扱うにはちょうどよい ) ような長さの列を見つけることができる。
ここでの $g([26,26,\dots,26])=big$ 、 $f([26,26,\dots,26]) = d$ とする。
とりあえず、 $g(B)=big-(d+1)$ なる列を探したくなる。このような $B$ に対しては、 $m = f(B)+1$ である。
もし $B$ としてどんな列でも使ってよいなら $[x,26,26,\dots,26]$ の $x$ を $26-d-1$ とすればよいが、全ての要素が $1$ 以上 $26$ 以下という縛りがあって困ってしまう。
増してや、 $g([x,26,26,\dots,26])=g(B)$ となる合法的な $B$ が存在しないかもしれない ( 例えば $p=50,x=0$ だと詰む )。
$g$ に対する要求をもう少し緩めたい。ここで、次のことが言える。
$big-2d \le g(B) \le big-(d+1)$ なる列 $B$ について、 $m=f(B)+(big-d)-g(B)$ が成り立つ。
直感的には、 $f([26,26,\dots,26])$ が $d$ だった ( $\mod m $ 上で $d$ だけ余裕がある ) ので、 $big-d$ からもう一度 $d$ を引いても 「 $big-d$ から余計に引いた数 + 余り $=m $ 」という性質を崩すことなく安全に引ける ( $big-d \rightarrow big-d-1$ 以外で $\mod m = 0$ となる数を跨ぎ超えることがない ) という感じ。
本当にひとことで理解を済ませるなら、「 $m $ で割った商を変えずに $d$ 引けるのだから、 $2d$ 引いても引きすぎにはならない」とでも言ったものか。
では、 $big-2d \le g(B) \le big-(d+1)$ なる列 $B$ はどう見つければよいのか? そもそも存在するのか?
$d=0$ である場合は不等式が偽だが、そう難しくない。要するに $f([26,26,\dots,26])=0$ なので、 $f([25,26,\dots,26])=m- 1 $ となりこれを尋ねてやればよい。
そして、 $d \ge 1$ である場合は $big-2d \le g(B) \le big-(d+1)$ なる列 $B$ が必ず存在する。証明の概略は次の通り。
- $0$ 要素目を $26-k_0$ とすることで $-k_0$ ( $0 \le k_0 \le 25$ ) が表現できる
- $1$ 要素目を $26-k_1$ とすることで $-p \times k_1$ ( $0 \le k_1 \le 25$ ) が表現できる
- $2$ 要素目を $26-k_2$ とすることで $-p^2 \times k_2$ ( $0 \le k_2 \le 25$ ) が表現できる
- $\vdots$
ここで $p \le 50$ が活きる。いったん $p=50$ として考えてみると
- $-1$ は $k=[1,0,0,\dots]$ として表現できる
- $-2$ は $k=[2,0,0,\dots]$ として表現できる
- $\vdots$
- $-25$ は $k=[25,0,0,\dots]$ として表現できる
- $-50$ は $k=[0,1,0,\dots]$ として表現できる
- $\vdots$
- $-1275$ は $k=[25,25,0,\dots]$ として表現できる
- $-2500$ は $k=[0,0,1,\dots]$ として表現できる
- $\vdots$
$p \le 50$ であるおかげで、表現できる数で隣り合ったもの $a,b$ について、 $2a \ge b$ が成り立っている ( $2$ 倍を超える差がつくことがない )。
これで存在性は示せた。
あとは $k$ の構築だが、これはかなり何をしてもできる ( $-(d+1)$ 以下で最大の表現を二分探索、後ろから貪欲 etc... 自分の実装は「後ろから貪欲」の方針 )。
Submission #271311959 - Codeforces
制約がちょっとずるい気もするが、常に誤差 $2$ 倍以内に収めることができる ( $d+1$ 以上 $2d$ 以下を引き去ることができる ) という点を上手く利用する点がかなり面白く感じた。
公式解説等にも同じことが書いてあるが、お気持ちが分かりづらかった(ここに書いたような理解をするとすんなり理解できた)のでメモ。
これ自力で思いつくにはどうすればいいんだろう 多分天才に生まれ直すのが一番早いと思います
$2$ 回目に $[26,26,\dots,26]$ を尋ねる発想は、「いずれ $f([26,26,\dots,26])+1$ くらいの数を引き去るという操作をしたいが、そのような操作を数列上で行えるようにする」というところから持ってこれるかもしれない。
