Codeforces Hello 2020 Writeup

C問題についてのみ書きます。

Hello 2020 C New Year and Permutation

問題

順列p_1, p_2, ..., p_nが与えられる。このとき、部分列[l,r]であってmax\(p_l,..,p_r\) - min\(p_l,..,p_r\) = r - lが成り立つものをframed segmentと呼ぶことにする。すべての長さNの順列に対して、framed segmentの数を数え上げてその和を素数Mで割った値を求めよ。

解法

順列が与えられて、それに対するframed segmentの数を数えるとO\(N!\)になってしまい計算量的に無理。そこで、視点を変えてサイズkのframed segmentを横断的に数え上げる方法を考える。
サイズkのframed segmentの位置、内部で使われる数の集合(順番は無視する)を考える。

p-1.png

図のように位置はスタート地点が1からn-k+1で全部でn-k+1通りある。
また、内部で使われる数は、r-l+1個の相異なる数の最大値と最小値の差がr-lであることから、連続したk個の数なので、これもスライドして考えるとn-k+1種類ある。

次に、framed segment外部と内部の順列を考える。これは、内部でk!通り、外部で\(n-k\)!通りである。

1 \leq k \leq nよりこれらを足し合わせてmで割れば答えが得られる。

実装

最後の足し合わせるところでO\(N\)であるので、N \leq 250000から各framed segmentのサイズごとはO\(\log N\)以下の計算量である必要がある。
ここで、factorialはf\(n\) = f\(n-1\) \times nであることを考えると、これは配列と非常に相性がよく、前計算をしてその配列を使えばよいとわかる。

vector<i64> fact(n+1);  
fact[0] = 1;  
for(i64 i=1;i<=n;i++)fact[i] = fact[i-1]*i%m;  
for (k=1;k<=n;k++){  
    res += (サイズkのframed segmentの数)  
}  

注意としては、サイズkのframed segmentの数を求める時のoverflowである。一つ掛けるごとにMODをとらなければ違う答えになってしまった。
計算量は前計算O\(N\), resに足し合わせてO\(N\)で全体でO\(N\)である。

コード

https://codeforces.com/contest/1284/submission/68567949

感想

はじめはMODが関わるライブラリゲーだと思ってmod_factorialなる関数を作ったが意味なかった。でもまた同じ思考になるかもしれないので、ライブラリのコメント欄に書いておいた。
ModInt理解したい。