P10893 题解

题意

有一个长 $n$ 的序列，我们分别从 $[1, n]$ 开始遍历，每次遍历到尾就跳到头继续。遍历开始时设一个变量 $cnt$，遍历时累加序列中的数。如若整个遍历过程中一直 $cnt > 0$，那么称这次遍历是“安全的”。

每次“安全的”遍历都会生成了一个长度为 $n$ 的新序列，将这些新序列按序列开头的数在原序列的位置从小到大排序，然后将它们拼接到一起，替换原序列。

我们再执行以上操作 $k$ 次，求最后一次操作找到了几个“安全的”遍历。

解法

先考虑 $k = 0$ 的情况。

看到遍历时要从尾跳到头，所以我们将原序列复制一遍接在后面，这个长 $2n$ 的序列记为 $a$。

看到遍历时要累加，我们记 $a$ 的前缀和为 $s$。

于是问题就转化为：求满足以下条件的正整数 $i$ 的个数：

• $n < i \le 2n$

• $\min_{j = i - n + 1}^{i} s_j > s_{i - n}$

一眼单调队列。

再将 $k > 0$ 的情况考虑。

我们分割 $s$。

设 $s = \overline{s_1s_2s_3}$。

假设 $\overline{s_2s_3s_1}$ 和 $\overline{s_3s_1s_2}$ 是“安全的”，连接在一起得到 $\overline{s_2s_3s_1s_3s_1s_2}$。

因为 $\overline{s_2s_3s_1}$ 和 $\overline{s_3s_1s_2}$ 是“安全的”，在连接后的序列中从第一个 $s_2$ 或第二个 $s_3$ 开始遍历是“安全的”。

由“安全的”的定义得 $\overline{s_3s_1s_2}$ 的前缀 $\overline{s_3s_1}$ 也是“安全的”，所以从第一个 $s_3$ 开始遍历也是“安全的”。同理，从第二个 $s_2$ 开始遍历也是“安全”的。

看得出来，如果第一次操作找到 $x$ 个“安全的”遍历。那第二次操作就会找到 $x^2$ 个“安全的”遍历，第三次就会找到 $(x^2)^2$ 个“安全的”遍历。最后一次是第 $(k + 1)$ 次。只需将最开始用单调队列求得的 $x$ 平方 $k$ 次即可。

代码：

#include <bits/stdc++.h>

#define int long long

//#define DEBUG

using namespace std;

#ifndef DEBUG
const int N = 2e6 + 10;
#else
const int N = 17;
#endif
const int mod = 998244353;

int n, k;
int s[N], a[N], maxn[N];
deque <int> q;

signed main ()
{
  cin >> n >> k;
  for (int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for (int i = n + 1; i <= 2 * n; i++)
    a[i] = a[i - n];
  for (int i = 1; i <= 2 * n; i++)
    s[i] = s[i - 1] + a[i];

  int res = 0;
  for (int i = 1; i <= 2 * n; i++)//单调队列
  {
    while (q.size () && q.front () + n <= i)
      q.pop_front ();
    while (q.size () && q.back () && s[i] <= s[q.back ()])
      q.pop_back ();
    q.push_back (i);
    if (i > n && s[q.front()] > s[i - n])
      res++;
  }
  for (int i = 1; i <= k; i++)
  {
    res *= res;
    res %= mod;
  }
  cout << res;
}