コンテンツにスキップ

ABC483 F - Sum of Mod of Linear

サイト
AtCoder
コンテスト
ABC483
問題
F - Sum of Mod of Linear
難易度
1868

NN 組の整数 (Ai,Bi)(A_i,B_i) が与えられます。各クエリの整数 xx に対し、

f(x)=∑i=1N((x+Ai) mod Bi)f(x) = \sum_{i=1}^{N} ((x+A_i) \bmod B_i)

を求める問題です(N≤5×105N \le 5 \times 10^5、Q≤2×105Q \le 2 \times 10^5、0≤Ai<Bi≤5×1050 \le A_i < B_i \le 5 \times 10^5、0≤x≤5×1050 \le x \le 5 \times 10^5)。

クエリごとに和を計算すると間に合わないので、X=5×105X=5\times 10^5 として、x=0,1,…,Xx=0,1,\dots,X の答えを先にすべて求めます。

11 組 (a,b)(a,b) に注目します。(x+a) mod b(x+a)\bmod b は、xx を 11 増やすたびに基本的には 11 増えます。ただし、x+ax+a が bb の倍数になるところでは b−1b-1 から 00 に戻るので、基本の増分 11 に加えて bb を引く必要があります。

この折り返しが起こる xx は

b−a, 2b−a, 3b−a,…b-a,\ 2b-a,\ 3b-a,\dots

です。全 NN 項を合わせると、毎回の基本の増分は NN になります。

そこで、ans[0] に f(0)=∑iAif(0)=\sum_i A_i を入れ、ans[1] 以降を NN で初期化します。各 (a,b)(a,b) について、b−ab-a から bb 刻みの位置で ans[x] から bb を引きます。最後に累積和を取ると、ans[x] が f(x)f(x) になります。

bb が小さい組は折り返しの回数が多いため、同じ (a,b)(a,b) を何度も処理すると時間がかかります。そこで、最初に同じ組の個数を数えます。(a,b)(a,b) が cc 個あるなら、初期値には acac を加え、折り返しの位置では bcbc を引けばよいです。

この工夫による計算量を考えます。bb を固定したとき、0≤a<b0 \le a < b なので、異なる組は高々 bb 種類です。また、11 組あたりの折り返しの回数は O(X/b+1)O(X/b+1) です。

境界を TT として分けると、b≤Tb \le T の組の処理は合計 O(XT+T2)O(XT+T^2)、b>Tb>T の組の処理は、組が高々 NN 個なので O(N(X/T+1))O(N(X/T+1)) です。TT を N\sqrt{N} 程度にすると、全体で O(XN+N)O(X\sqrt{N}+N) 回の処理に抑えられます。

コードで使う Counter の構築には O(Nlog⁡N)O(N\log N) かかるので、累積和とクエリへの回答も含めた計算量は O(Nlog⁡N+XN+Q)O(N\log N+X\sqrt{N}+Q)、空間計算量は O(N+X)O(N+X) です。答えは 32 bit 整数に収まらない場合があるので、64 bit 整数を使います。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/counter.hpp"
void solve() {
constexpr ll XMAX = 5e5;
LL(N);
VAL(AB, N, 2);
Counter<al<2>> cnt(AB);
vl ans(XMAX + 1, N);
ans[0] = 0;
for (auto [ab, c] : cnt) {
auto [a, b] = ab;
ans[0] += a * c;
rep(x, b - a, XMAX + 1, b) {
ans[x] -= b * c;
}
}
rep(x, 1, XMAX + 1) {
ans[x] += ans[x - 1];
}
LL(Q);
rep(Q) {
LL(x);
print(ans[x]);
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

実装では、自作ライブラリの Counter で同じ組の個数を数えています。累積和を取る前の ans[x] (x≥1x \ge 1) は答えの差分、累積和を取った後は各 xx に対する答えです。