QOJ #8147. Math Exam 题解

Description

求序列 $a_{1\cdots n}$ 的个数，满足：$|a_i|\le m$ 且 $4\sum_{j=1}^i a_j=(a_i+1)^2$。

$1\le n\le 10^7$，$1\le m\le 2n$，$m$ 是奇数。

Solution

首先推一下式子会发现 $a_1=1$，$\forall i\geq 2,a_i=a_{i-1}+2$ 或者 $-a_{i-1}$。

注意到 $a_i=-a_{i-1}$ 这个东西很难刻画，考虑转成绝对值。

记 $b_i=\frac{|a_i+1|}{2}$，则 $b_{i+1}=b_i\pm 1$，并且 $0\leq b_i\leq\frac{|m+1|}{2}$。

对于 $a_i\geq -1$，如果 $b_{i+1}=b_i+1$，则钦定 $a_{i+1}=a_i+2$，否则钦定 $a_{i+1}=-a_i$。

对于 $a_i<-1$，如果 $b_{i+1}=b_i+1$，钦定 $a_{i+1}=-a_i$，否则钦定 $a_{i+1}=a_i+2$。

经过计算会发现一组值域在 $\left[0,\frac{|m+1|}{2}\right]$ 且 $b_1=1$ 的 $b$ 恰好一一对应一组 $a$。

然后就转成了有上下界的格路计数问题，用反射容斥做即可。

时间复杂度：$O(n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e7 + 5, kMod = 998244353;

int n, m;
int fac[kMaxN], ifac[kMaxN], s[kMaxN];

int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

int C(int m, int n) {
  if (m < n || m < 0 || n < 0) return 0;
  return 1ll * fac[m] * ifac[n] % kMod * ifac[m - n] % kMod;
}

void prework(int n = 1e7) {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % kMod;
  ifac[n] = qpow(fac[n]);
  for (int i = n; i; --i) ifac[i - 1] = 1ll * ifac[i] * i % kMod;
}

int S(int l, int r) {
  l = std::max(l, 0), r = std::min(r, n);
  return l <= r ? sub(s[r], !l ? 0 : s[l - 1]) : 0;
}

int calc(int n, int l, int r, int L, int R) {
  l += n, r += n;
  if (l % 2 != 0) ++l;
  if (r % 2 != 0) ++r;
  l /= 2, r /= 2;
  int ret = 0;
  for (int k = -((n + R) / (R - L)); k <= (n + R) / (R - L); ++k) {
    inc(ret, sub(S(l + k * (R - L), r + k * (R - L)), S(l + k * (R - L) - R, r + k * (R - L) - R)));
  }
  return ret;
}

void dickdreamer() {
  std::cin >> n >> m; --n;
  for (int i = 0; i <= n; ++i) s[i] = add(!i ? 0 : s[i - 1], C(n, i));
  std::cout << calc(n, -1, (m + 1) / 2 - 1, -2, (m + 1) / 2) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  prework();
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}