https://atcoder.jp/contests/agc007/submissions/21896735
の公式が成り立つ理由
結論から言うと が答えになる。
に比べて
の制約が非常に緩いことから、ある程度の余裕を持たせて昇順数列 a を考えたほうが良いのかな、という気持ちになる。
公式のように例えば M=30000 の等差で昇順・降順の a と b を作って加算してみると全ての合計が同じになる。ここで a に
の
だけ順番に加算していくと元々全ての合計が同じだったため
の合計が p の順番になってくれる。このとき M が N に比べて十分に大きければ a の昇順が崩れることもない。
感想: 気づけそうで自力で気づくのは難しい…
