当前位置: 首页 > news >正文

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_tconst 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 ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::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;
}
http://www.hskmm.com/?act=detail&tid=23633

相关文章:

  • 10.03模拟赛t3
  • 国庆梦熊集训做题记录
  • 文件的逻辑结构
  • python 肘部法则,判点聚类分为几类,K-means聚类分析
  • AT_abc315_f [ABC315F] Shortcuts
  • 紫外UV固化太阳光模拟器的原理 - 教程
  • 每日一题
  • P5709 【深基2.习6】Apples Prologue / 苹果和虫子
  • 问题表 - microsoft
  • Leetcode 736. Lisp 语法解析
  • Day10.1
  • SolarWinds Web Help Desk远程代码执行漏洞分析
  • Aria2安装
  • 正则表达式学习
  • 深入解析:[特殊字符]函数指针:C语言的动态灵魂,嵌入式的超能力(202589)
  • 《电路基础》第八章学习笔记
  • 《电路基础》第七章学习笔记
  • LLM大模型:deepseek sparse attention是个啥?
  • Day10
  • 软著申请全流程材料模板,2025年最新模板汇总! - 实践
  • 手把手教你使用 Docker 部署 Nginx 教程
  • CF2129 CF1951 VP 记录
  • PWN-BUUCTF-test_your_nc
  • 详细介绍:计算机视觉:OpenCV+Dlib 人脸检测
  • python 老生常谈的找2个excel相同列的行,把其中一个excel行的对应的值放入到另一个excel中
  • 实用指南:淘宝团购上线:本地生活的“两种解法”
  • 【K8S】Kubernetes 调度器深度解析:原理与源码分析
  • 快速幂算法的基础和扩展
  • 堆叠集成
  • 概率与决策 - 模拟程序让你在选择中取胜