技巧性比较强的题(?
设 \(a\) 为最优解的 \(A\),则 \(a\) 可以贪心构造,就是每一位都取到下界。
考虑设 \(b_i = \frac{a_i}{i}\),因为 \(i \times b_i < (i + 1) \times b_{i+1}\),则 \(b_{i+1} = \left\lfloor\frac{i \times b_i}{i+1}\right\rfloor + 1 = b_i - \left\lceil\frac{b_i}{i+1}\right\rceil + 1\),得到 \(b_i - b_{i+1} = \left\lceil\frac{b_i}{i+1}\right\rceil - 1\),所以 \(b\) 不增。
考虑 \(b_i\) 一个比较宽松的上界:
发现 \(b_i\) 的减小速度大致会越来越平缓。考虑类根号分治,观察 \(b_i - b_{i+1}\),发现它只有 \(O(X^{\frac{1}{3}})\) 种取值。证明:
- \(i \le X^{\frac{1}{3}}\),\(b_i - b_{i+1}\) 有 \(O(X^{\frac{1}{3}})\) 种取值;
- \(i > X^{\frac{1}{3}}\),\(b_i - b_{i+1} = \left\lceil\frac{b_i}{i+1}\right\rceil - 1 < \left\lceil\frac{\frac{X}{i}+i}{i+1}\right\rceil = O(X^{\frac{1}{3}})\),有 \(O(X^{\frac{1}{3}})\) 种取值。
考虑对极长等差连续段 \([l,r]\) 计算。设 \(b_l - b_{l+1} = b_{l+1} - b_{l+2} = \cdots = b_{r-1} - b_r = k\),我们希望计算 \(\sum\limits_{i=l}^r a_i\)。
设 \(f(x) = \sum\limits_{i=1}^x i = \frac{i(i+1)}{2}\),\(g(x) = \sum\limits_{i=1}^x i^2 = \frac{i(i+1)(2i+1)}{6}\),得到:
至此可以 \(O(1)\) 计算极长等差连续段的 \(\sum\limits_{i=l}^r a_i\)。
现在问题是知道左端点 \(l\),如何求极长等差连续段的右端点 \(r\)。我们有 \(b_{r-1} - b_r = b_l - b_{l+1}\),即 \(\left\lceil\frac{b_l + (l-r+1)(\left\lceil\frac{b_l}{l+1}\right\rceil-1)}{r}\right\rceil = \left\lceil\frac{b_l}{l+1}\right\rceil\),可以二分得到 \(r\)。
总时间复杂度 \(O(TX^{\frac{1}{3}} \log N)\),优化二分上界后可以通过。
code
// Problem: E - Sequence of Multiples
// Contest: AtCoder - AtCoder Regular Contest 135
// URL: https://atcoder.jp/contests/arc135/tasks/arc135_e
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2, inv6 = 166374059;
ll n, m;
inline ll f(ll x) {
x %= mod;
return x * (x + 1) % mod * inv2 % mod;
}
inline ll g(ll x) {
x %= mod;
return x * (x + 1) % mod * (x * 2 + 1) % mod * inv6 % mod;
}
inline ll calc(ll l, ll r, ll b, ll k) {
ll res = (b + k * l % mod) % mod * (f(r) - f(l - 1) + mod) % mod;
res = (res - k * (g(r) - g(l - 1) + mod) % mod + mod) % mod;
return res;
}
void solve() {
scanf("%lld%lld", &n, &m);
ll p = 1, lst = 0, ans = 0;
while (p <= n) {
ll cur = (p == 1 ? m : lst - (lst + p - 1) / p + 1);
if (p == n) {
ans = (ans + cur * p % mod) % mod;
break;
}
ll nxt = cur - (cur + p) / (p + 1) + 1;
ll l = p, r = (cur == nxt ? n - 1 : min(n - 1, p + cur / (cur - nxt))), pos = -1, x = (cur + p) / (p + 1);
while (l <= r) {
ll mid = (l + r) >> 1;
if (x == (cur + (p - mid) * (x - 1) + mid) / (mid + 1)) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ans = (ans + calc(p, pos + 1, cur, (cur - nxt + mod) % mod)) % mod;
lst = cur + (pos + 1 - p) * (nxt - cur);
p = pos + 2;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Multiples Sequence AtCoder Regular Contestmultiples sequence atcoder regular visibility sequence atcoder regular atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder