エクサウィザーズ2019-D:Modulo Operations

めちゃくちゃ時間をかけてしまったけどこういうのが通せるようになったのは成長かな...。

問題

考察過程・解法

　確率に落とすのは苦手なので総和のままやった。
　まず最初に， $s_i\lt s_j$ という2つの集合の要素について， $s_i$ で余りをとった値に， $s_j$ で余りをとってもその値は変わらないことに気付こう。したがって， $s$ をソートして新たに番号を振り直すことにする。すると， $s_1,s_2,\cdots,s_i$ を作ってできた値を $v$ とすると， $v$ は $s_{i+1},\cdots,s_N$ たちの影響を受けない。このことを用いて，dpを組み立てていこう。
　 $dp_{i,j}$ を「黒板に $j$ が書かれている状態から始めて， $s_1,s_2,\cdots,s_i$ のみを選んで操作をしたときの，最後に黒板に書かれる数字の総和」としよう。こうすると， $dp_{i-1,X (\mathrm{mod} s_i)}\times {}_{N-1} \mathrm{P} _{N-i}$ の $i$ についての総和が答えとなる。この理由を説明しよう。 $s_i$ を先頭にすると決め打つと，次に書かれる数は $X (\mathrm{mod} s_i)$ となる。そこからの操作はどうなるかというと， $s_1$ から $s_{i-1}$ までの順番は $dp$ の部分に表現されているから，残りの $N-i$ 個の並べ方だけが自由である。従って，上の式が「 $s_i$ を最初に選んだ時の，最後に黒板に書かれる数の総和」を表しており，これを $i=1,2,\cdots,N$ について足し合わせれば，すべての順列について考えたことになる。
　最後にdpの遷移を考えよう。 $j$ が黒板に書かれているとして，使える数が $s_{i-1}$ までから $s_i$ までに増えたときに，どのような操作が可能になるだろうか？まず，最初に $s_i$ を選ぶとすると，黒板の数は $j (\mathrm{mod} s_i)$ となるから，その後の操作によってできる数の総和はもちろん $dp_{i-1,j (\mathrm{mod} s_i)}$ となる。最初に $s_{i-1}$ 以下の数を選ぶとすると，その後の操作によってできる数の総和は $dp_{i-1,j}\times (i-1)$ となる。 $i-1$ がかかっているが，最初に $s_{i-1}$ 以下の数を選んだので， $s_i$ はどのタイミングで選んでも総和には影響しない。よって， $s_i$ を入れるタイミングの数だけ $dp_{i-1,j}$ が加算されるということになる。
　計算量は $O(NX)$ であり，C++なら十分間に合う。Pythonだと心配。

実装

Submission #4777838 - ExaWizards 2019

$i=1$ のときだけ注意。もうちょっとうまく書けるかも。

最近調子が良いので黄色が見えてきた。