自己出的一道题

发布于

题意

给定长度为 $n$ 的数组,求:
$$\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=i}^n \gcd\left\{a_i, a_{i + 1}, \ldots, a_j\right\}$$
对 $998244353$ 取模。

题解

对于这个问题,$\gcd$ 是单调递减的,因此可以使用 ST 来维护区间 $\gcd$,统计答案时对于每个 $\gcd$ 值,乘以对应区间长度即可。

显然这不够难!

考虑加强一下:
$$\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=i}^n \gcd\left\{a_i, a_{i + 1}, \ldots, a_j\right\} \cdot \max\left\{a_i, a_{i + 1}, \ldots, a_j\right\}$$

好的,发现原题了 https://www.luogu.com.cn/problem/P9607

题解

还是很简单,在一段区间里,最大值是不会改变的。所以对于每个最大值,乘上对应 $\gcd$ 值和长度,就是这个值的贡献。线段树维护最大值即可。

代码

// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// Only one ace left.

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define _CONSOLE 0
// #define EFILE ""

using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;

template <typename _Type, size_t _Size>
struct mray : array<_Type, _Size + 9> {
  _Type& operator[](size_t index) { return this->at(index); }
};

// Defines

// Constants
constexpr tp Hat_N = 5e5, mod = 998244353;

// Classes
struct Seg_Tree {
  mray<tp, Hat_N * 4> laz;
  mray<tp, Hat_N * 4> val;

  void push(tp x) { val[x] = (val[x << 1] + val[x << 1 | 1]) % mod; }

  void pull(tp x, tp l, tp r) {
    if (laz[x]) {
      tp mid = l + r >> 1;
      laz[x << 1] = laz[x << 1 | 1] = laz[x];
      val[x << 1] = laz[x] * (mid - l + 1) % mod;
      val[x << 1 | 1] = laz[x] * (r - mid) % mod;
      laz[x] = 0;
    }
  }

  void build(tp x, tp l, tp r) {
    tp mid = l + r >> 1;
    laz[x] = val[x] = 0;
    if (l == r) return;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    push(x);
  }

  void modify(tp x, tp l, tp r, tp ml, tp mr, tp k) {
    if (l <= ml && mr <= r) {
      val[x] = k * (mr - ml + 1);
      laz[x] = k;
    } else {
      tp mid = ml + mr >> 1;
      pull(x, ml, mr);
      if (l <= mid) modify(x << 1, l, r, ml, mid, k);
      if (r > mid) modify(x << 1 | 1, l, r, mid + 1, mr, k);
      push(x);
    }
  }
  
  tp query(tp x, tp l, tp r, tp ml, tp mr) {
    if (l <= ml && mr <= r) return val[x];
    else {
      tp mid = ml + mr >> 1, ans = 0;
      pull(x, ml, mr);
      if (l <= mid) ans += query(x << 1, l, r, ml, mid);
      if (r > mid) ans += query(x << 1 | 1, l, r, mid + 1, mr);
      return ans % mod;
    }
  }
} tre;

// Typedeves

// Variables
tp n, ans;

// Arrays
stack<tp> stk;
mray<tp, Hat_N> lg, pmav;
mray<mray<tp, 17>, Hat_N> st;

// Functions
void MIST() {
}

// :/

tp gcd(tp a, tp b) { return !b ? a : gcd(b, a % b); }

void STP() {
  tp k = log2(n / 2) + 1;
  lg[1] = 0;
  for (tp i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (tp j = 1; j <= k; ++j) {
    for (tp i = 1; i + (1ll << j) - 1 <= n; ++i) st[i][j] = gcd(st[i][j - 1], st[i + (1ll << j - 1)][j - 1]);
  }
}

tp sgcd(tp l, tp r) {
  tp k = lg[r - l + 1];
  return gcd(st[l][k], st[r - (1ll << k) + 1][k]);
}

void calc(tp x, tp h) {
  if (x <= 0) return;
  tp l = 1, r = x - 1, g = sgcd(x, h);
  while (l <= r) {
    tp mid = l + r >> 1;
    if(sgcd(mid, h) == g) r = mid - 1;
    else l = mid + 1;
  }
  ans = (ans + tre.query(1, l, x, 1, n) * g) % mod;
  calc(l - 1, h);
}

void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
  cin >> n;
  tre.build(1, 1, n);
  for (tp i = 1; i <= n; ++i) cin >> st[i][0];
  for (tp i = 1; i <= n; ++i) {
    while (stk.size() && st[stk.top()][0] < st[i][0]) stk.pop();
    pmav[i] = stk.empty() ? 1 : stk.top() + 1;
    stk.push(i);
  }
  STP();
  for (tp i = 1; i <= n; ++i) {
    tre.modify(1, pmav[i], i, 1, n, st[i][0]);
    calc(i, i);
  }
  cout << ans << '\n';
}

#include <fstream>

signed main() {
  tp t = 0, _t = 1;
  cin.tie(0)->sync_with_stdio(0);
#if !_CONSOLE
#ifdef _LOCAL
  static ifstream _in("input.in");
  cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
  static ifstream _in(EFILE ".in");
  static ofstream _out(EFILE ".out");
  cin.rdbuf(_in.rdbuf());
  cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
  // cin >> _t;
  MIST();
  while (t < _t) STRUGGLING(++t);
  return 0;
}

//*/

显然这还是不够难!

送你一道难题吧。

定义对正整数 $x$ 的一次变换为:在集合 $\{-1, 1\}$ 中等概率随机一个变量 $k$,让 $x$ 变为变为 $x + k \cdot \operatorname{lowbit}\left(x\right)$。

定义 $f\left(x\right)$ 表示正整数 $x$ 变换为 $0$ 的期望步数。如果期望步数不是整数,设期望步数的最简分数为 $\frac pq$,则以 $p \cdot q^{-1}$ 表示。其中 $q^{-1}$ 表示 $q$ 在取模意义下的逆元。

求 $\displaystyle\sum\limits_{i=l}^r f\left(i\right)$
答案对 $998244353$ 取模。

$l \leq r \leq 10^{18}$


暂无评论

发表评论