模拟赛题讲解[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;
}