模拟赛题讲解[30]
来自 s_r_f 2023-08-03 noi.ac #3198
题目描述:
小 D 有 $n$ 个没有刻度的杯子,每个杯子的容积为一个整数 $a_i$。
假设有无限的水,他想知道对于每个区间 $[l,r]$ $(1\leq l\leq r \leq n)$ ,在只有这个区间里的杯子的情况下,能精准测量出的最小容积。
可以证明最小容积一定是整数。
你只需要输出所有区间的答案总和。答案对 998244353 取模。
精确测量是指,倒水的过程没有损耗,且只能以把某个杯子倒满 / 倒空作为一次倒水的结束状态
输入格式:
第一行,一个正整数 $n$
第二行, $n$ 个正整数 $a_1,a_2,…a_n$
输出格式:
输出一行一个整数,表示所有区间的答案总和对 998244353 取模的结果。
输入样例:
5
3 2 1 3 2
输出样例:
21
数据范围:
子任务 1(10pts) : $n \leq 10,a_i \leq 3$
子任务 2(20pts) $:$ $a_i \leq 3$
子任务 3(20pts) $:$ $n \leq 1000$
子任务 4(50pts) : $n \leq 10^5,1 \leq a_i \leq 10^9$
题解:
稍微试一试可以一个区间能测出来的就是他们的 $\gcd$ ,证明我也不是很会(有空再说吧)。
区间求 $\gcd$ 可以用 ST 表维护,然后总和可以用二分,这个我在以前的题讲过,
因为每 $\gcd$ 和右边的数一次,要么不变,要么至少减半,所以这个的值域是 $\log$ 级的,可以二分暴力维护。
时间复杂度 $\mathcal{O}(n \log a^2)$
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }
#define N ((int)(1e5 + 15))
int n, ans, a[N], lg[N], st[18][N];
int query(int l, int r)
{
int k = lg[r - l + 1];
return gcd(st[k][l], st[k][r - (1 << k) + 1]);
}
int solve(int L,int i, int v)
{
int l = L, r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(query(i, mid) >= v) l = mid; else r = mid - 1;
}
return l;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++) { cin >> a[i]; st[0][i] = a[i]; }
for(int i = 2; i <= N - 10; i++) lg[i] = lg[i >> 1] + 1;
for(int j = 0; 1 << (j + 1) <= n; j++)
{
int *f = st[j], *g = st[j + 1];
for(int i = 1; i + (1 << j) - 1 <= n; i++)
g[i] = gcd(f[i], f[i + (1 << j)]);
}
for(int i = 1; i <= n; i++)
{
int L = i, g = a[i]; // L 为 第一个
while(L <= n) {
int tL = solve(L, i, g) + 1;
add(ans, g * (tL - L) % mod); L = tL, g = query(i, L);
}
}
cout << ans << '\n';
return 0;
}
对了,可能有人不会写 $\mathcal{O}(n^2)$ 的暴力,我也贴一下吧(
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }
#define N ((int)(1e3 + 15))
int n,ans,a[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("data.in","r",stdin);
// freopen("std.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++)
{
int g = a[i];
for(int j = i; j >= 1; j--) {
g = gcd(g, a[j]); add(ans, g % mod);
}
}
cout << ans << '\n';
return 0;
}