競技プログラミング用 知識集積所
ABC452E - You WILL Like Sigma Problem
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
愚直にやったらTLEではあるが、
S(j)=Σ[i] A[i]*(i%j)
を高速で求めることは実はそんなに難しくない。
よって、各jについてそれを実行し、
よって、各jについてそれを実行し、
Σ[j] B[j]*S(j)
の方の総和を愚直に足し算しても十分間に合う。
例えば、j=3である場合、
S(3) = A[1]*1 + A[2]*2 + A[3]*0 + A[4]*1 + A[5]*2 + A[6]*0 + ……
であるが、これは
S(3) = ( A[1]*1 + A[2]*2 + A[3]*3 + A[4]*4 + A[5]*5 + A[6]*6 + …… )
- 3*( A[3] + A[4] + A[5] + A[6] + …… )
- 3*( A[6] + …… )
- ……
と変形できる。
最初の和は一度計算すればjの値によらないので使いまわせる。
2つめ以降の総和は、累積和を使えばすぐ。
引き算の回数はN/j回なので、S(1)からS(M)まで全部求めるなら合計NlogM回。
よって計算量はO(M+NlogM)で、間に合う。
最初の和は一度計算すればjの値によらないので使いまわせる。
2つめ以降の総和は、累積和を使えばすぐ。
引き算の回数はN/j回なので、S(1)からS(M)まで全部求めるなら合計NlogM回。
よって計算量はO(M+NlogM)で、間に合う。
答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
