ABC483 F - Sum of Mod of Linear
- サイト
- AtCoder
- コンテスト
- ABC483
- 問題
- F - Sum of Mod of Linear
- 難易度
- 1868
組の整数 が与えられます。各クエリの整数 に対し、
を求める問題です(、、、)。
答えの差分を作る
Section titled “答えの差分を作る”クエリごとに和を計算すると間に合わないので、 として、 の答えを先にすべて求めます。
組 に注目します。 は、 を 増やすたびに基本的には 増えます。ただし、 が の倍数になるところでは から に戻るので、基本の増分 に加えて を引く必要があります。
この折り返しが起こる は
です。全 項を合わせると、毎回の基本の増分は になります。
そこで、ans[0] に を入れ、ans[1] 以降を で初期化します。各 について、 から 刻みの位置で ans[x] から を引きます。最後に累積和を取ると、ans[x] が になります。
同じ組をまとめて処理する
Section titled “同じ組をまとめて処理する”が小さい組は折り返しの回数が多いため、同じ を何度も処理すると時間がかかります。そこで、最初に同じ組の個数を数えます。 が 個あるなら、初期値には を加え、折り返しの位置では を引けばよいです。
この工夫による計算量を考えます。 を固定したとき、 なので、異なる組は高々 種類です。また、 組あたりの折り返しの回数は です。
境界を として分けると、 の組の処理は合計 、 の組の処理は、組が高々 個なので です。 を 程度にすると、全体で 回の処理に抑えられます。
コードで使う Counter の構築には かかるので、累積和とクエリへの回答も含めた計算量は 、空間計算量は です。答えは 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] () は答えの差分、累積和を取った後は各 に対する答えです。