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

NOIP模拟赛 十七

A.

对于一个 \(x\) ,如果 \(x\bmod a < x\) ,称其为有效的。我们断言,有效次取模只会发生 \(\log\) 次。

如果发生有效取模,则 \(a<x\)

  • \(a\le \frac{x}{2}\)\(x\bmod a <a<\frac{x}{2}\)
  • \(a>\frac{x}{2}\) ,则 \(x \bmod a \le x-a<\frac{x}{2}\)

所以每发生一次有效取模,\(x\) 至少减半。

使用倍增维护第一个可以发生有效取模的位置,复杂度 \(O(n\log^2 n)\)

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inlineconst int LN = 2e5 + 7;
const int mod = 1e9 + 7;
typedef long long ll;int n, q, t, ans, fa[21][LN], stk[LN], tp, rmb[LN]; ll a[LN];il int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
il void upa(int& u, int v) { u = add(u, v); }
il int mul(ll u, ll v) { return u * v >= mod ? u * v % mod : u * v; }
il void upm(int& u, int v) { u = mul(u, v); }
int qry(int u, ll r) {if (r <= 1) return r > 0;if (!u) return __int128(r) * (r + 1) / 2 % mod;if (r < a[u]) {rep(i, 20, 0) if (r < a[fa[i][u]]) u = fa[i][u];return qry(fa[0][u], r);}if (r % a[u] == a[u] - 1) return mul(r / a[u] % mod + 1, rmb[u]);return add(mul(r / a[u] % mod, rmb[u]), qry(fa[0][u], r % a[u]));
}int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);ll l, r; int p;std::cin >> n >> q >> t;lep(i, 1, n) std::cin >> a[i];tp = 1;rep(i, n, 1) {while (tp and a[i] <= a[stk[tp]]) --tp;fa[0][i] = stk[tp];lep(j, 1, 20) fa[j][i] = fa[j - 1][fa[j - 1][i]];stk[++tp] = i, rmb[i] = qry(fa[0][i], a[i] - 1);}while (q--) {std::cin >> l >> r >> p; p = (p + t * ans) % n + 1;std::cout << (ans = add(qry(p, r), mod - qry(p, l - 1))) << '\n';}return 0;
}

B.

Link

C.

题目等价于计数满足长度为 \(m\) ,满足 \(0\le x_i \le b^i - c\)\(\sum_{i=1}^mx_i<n\)

\(n-1\) 变成 \(\le n\)

插板法容斥掉 \(x_i\) 的上界限制。

对于有 \(n\) 个相同的球可用,放入 \(m\) 个不同的盒子里,不可空的方案数。

可以新建第 \(m+1\) 个盒子,转入这个盒子的表示不要。

多放一个球在最后一个盒子,因为最后一个盒子是可空的。

则方案数为 \({n\choose m}\)

转变为可空,则方案数为 \({n+m\choose m}\)

\[ans=\sum_{S\subseteq \{1,2,\cdots,m\}}(-1)^{\left|S\right|}{n+m-\sum_{i\in S}(b^i-c+1)\choose m} \]

固定 \(\left|S\right|=k\) ,则

\[ans=\frac{1}{m!}\sum_{S\subseteq \{1,2,\cdots,m\},\left|S\right|=k}(-1)^{\left|S\right|}(n+m+k(c-1)-\sum_{i\in S}b^i)^{\underline{m}} \]

将常量使用 \(A\) 表示,\(F(k)\) 表示 \(\left|S\right|=k\) 时的答案,则

\[ans=\frac{1}{m!}\sum_{k=0}^m (-1)^kF(k)\\ F(k)=\sum_{S\subseteq\{1, 2,\cdots,m\},\left|S\right|=k}(A-\sum_{i\in S}b^i)^{\underline m} \]

如果记 \(\sum_{i\in S}b^i=x\) ,则 \(F(k)\) 可以表示为一个关于 \(x\)\(m\) 次多项式 \(F(k)=\sum_{i=0}^m a_ix^i\)

注意保证 \(A\) 要不小于 \(x\)

那么我们的问题就变成了两部分,计算系数 \(a_k\) 以及 \((\sum_{i\in S}b^i)^k\)

先来看 \(a_k\) ,可以朴素 dp 求出,总共有 \(m\) 个括号。

每个括号可以选择乘上常数,或者乘上 \(-x\) 。直接转移即可。

\(\sum_{i\in S}b^i\) 仍旧考虑 dp ,首先把 \(A\) 的限制丢掉。

\(f[i, j, k]\) 表示考虑前 \(i\) 个元素,\(\left|S\right|=j, (\sum_{i\in S}b^i)^k\) ,二项式定理转移。

\[f[i,j,k]=\sum_{t=0}^k{k\choose t}f[i-1,j,t]\times b^{i(k-t)} \]

那么加上 \(A\) 的限制呢?

\(A\) 看作一个 \(b\) 进制的数,那么限制便类似数位 dp 的上界,加维 \(0/1\) 表示是否顶上界即可。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 100 + 7;
const int mod = 998244353;
typedef long long ll;
typedef std::vector <ll> Big;
typedef std::string Str;
typedef std::pair<int, int> PII;bool FIRPOS;int m, b, c, f[LN][LN][LN][2], g[LN][LN], pw[LN * LN], A, C[LN][LN]; Big n; Str s;bool ENDPOS;Big operator + (Big a, ll x) {Big c = a; c[0] += x;if (x >= 0) {lep(i, 0, (int)c.size() - 1) {x = c[i] / b; if (!x) break;((i + 1) == c.size()) and (c.emplace_back(0), 1);c[i + 1] += x, c[i] %= b;}} else {lep(i, 0, (int)c.size() - 1) {if (c[i] >= 0) break; if (i + 1 == c.size()) return { -1 };x = (b - c[i] - 1) / b, c[i + 1] -= x, c[i] += x * b;}}return c;
}
Big operator * (Big a, ll x) {Big c = a; for (ll& v : c) v *= x; int len = c.size();lep(i, 0, (int)c.size() - 1) {x = c[i] / b; if (i >= len and !x) break;(i + 1 == c.size()) and (c.emplace_back(0), 1);c[i + 1] += x, c[i] %= b;}return c;
}
Big Change(Str s) { Big ans; ans.emplace_back(0);lep(i, 0, (int)s.size() - 1) ans = ans * 10, ans = ans + (s[i] - '0');while (ans.size() <= m) ans.emplace_back(0);return ans;
}
il int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
il void upa(int& u, int v) { u = add(u, v); }
il int mul(ll u, ll v) { return u * v >= mod ? u * v % mod : u * v; }
il void upm(int& u, int v) { u = mul(u, v); }
il int MyPow(int a, int b) { int ans = 1; for (; b; b >>= 1, upm(a, a)) if (b & 1) upm(ans, a); return ans; }
void tran() {lep(i, 0, (int)s.size() - 1) A = add(mul(A, 10), s[i] - '0');upa(A, mod + m - 1), n = n + (m - 1);
}int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();lep(i, 0, LN - 1) { C[i][0] = 1;lep(j, 1, i) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);}std::cin >> m >> b >> c >> s; n = Change(s), tran();pw[0] = 1; lep(i, 1, LN * LN - 1) pw[i] = mul(pw[i - 1], b);int tmp, ans = 0;lep(K, 0, m) {std::memset(g, 0, sizeof(g)); g[0][0] = 1;lep(i, 1, m) lep(j, 0, i) {g[i][j] = mul(g[i - 1][j], A - i + 1);if (j) upa(g[i][j], mod - g[i - 1][j - 1]);}std::memset(f, 0, sizeof(f));int op = 0;lep(i, m + 1, (int)n.size() - 1) gmx(op, n[i]);if (op) f[m + 1][0][0][0] = 1;else f[m + 1][0][0][1] = 1;rep(i, m, 1) {lep(j, 0, m) lep(k, 0, m) {if (n[i] > 1) {f[i][j][k][0] = add(f[i + 1][j][k][0], f[i + 1][j][k][1]);if (j) lep(p, 0, k) upa(f[i][j][k][0], mul(mul(add(f[i + 1][j - 1][p][0], f[i + 1][j - 1][p][1]), C[k][p]), pw[i * (k - p)]));}else if (n[i] == 1) {f[i][j][k][0] = add(f[i + 1][j][k][0], f[i + 1][j][k][1]);if (j) lep(p, 0, k) {upa(f[i][j][k][0], mul(mul(f[i + 1][j - 1][p][0], C[k][p]), pw[i * (k - p)]));upa(f[i][j][k][1], mul(mul(f[i + 1][j - 1][p][1], C[k][p]), pw[i * (k - p)]));}}else {f[i][j][k][0] = f[i + 1][j][k][0], f[i][j][k][1] = f[i + 1][j][k][1];if (j) lep(p, 0, k) upa(f[i][j][k][0], mul(f[i + 1][j - 1][p][0], mul(C[k][p], pw[i * (k - p)])));}}}tmp = 0;lep(i, 0, m) upa(tmp, mul(g[m][i], add(f[1][K][i][0], f[1][K][i][1])));(K & 1) ? upa(ans, mod - tmp) : upa(ans, tmp);n = n + (c - 1); (c - 1 >= 0) ? upa(A, c - 1) : upa(A, mod + c - 1);if (n[0] < 0) break;}int inv = 1;lep(i, 1, m) upm(inv, i); inv = MyPow(inv, mod - 2);upm(ans, inv);std::cout << ans << '\n';#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

http://www.hskmm.com/?act=detail&tid=19371

相关文章:

  • day22_用户模块
  • 2025 丹东店推荐:丽格门窗,用 20 年技术沉淀守护家的舒适
  • NOIP2025模拟赛23
  • step
  • 2025 呼和浩特店推荐:丽格门窗,用 20 年技术沉淀守护家的温度
  • 深入解析:浏览器端音视频处理新选择:Mediabunny 让 Web 媒体开发飞起来
  • 2025 宁波门窗店推荐:丽格门窗,甬城品质家居的安心之选
  • 2025 贵阳门窗店优选:丽格门窗,用 20 年匠心适配高原宜居需求
  • 2025 济南门窗店选购指南:丽格门窗凭硬实力圈粉品质家庭
  • “鹏云杯”第十二届山东省大学生网络安全技能大赛 -- Crypto -- WriteUp
  • 服务器系统时间不对?Linux系统时间修改与同步全面指南
  • 9/27
  • 2025 常熟门窗店优选:丽格门窗,20 年技术沉淀的品质之选
  • 2025上海门窗店选购选丽格!20 年系统门窗经验,徐汇宜山路店品质之选
  • 实用指南:Apache、Nginx 和 Tomcat 的区别
  • python+uniapp基于微信小程序美食点餐实用的系统
  • JavaDoc
  • parted command for linuxg
  • 如何在不绑定Apple账号的情况下备份florr.io
  • AI智能体框架怎么选?7个主流工具详细对比解析
  • 原创OI试题 - L
  • 《深入浅出WPF》:8.3.2 自定义路由事件 事件注册类型为 EventHandlerReportTimeEventArgs,但.NET 事件包装器类型为 RoutedEventHandler
  • day 6
  • 2025 自动售货机工厂推荐 配备 Bystronic 激光切割机,快速周转准时交货
  • 7.WPF 的 TextBox 和 TextBlock 控件 - 实践
  • 从中序与后序遍历序列构建二叉树的迭代解法
  • 安装 HuggingFace datasets 模块、包、库
  • 使用 SignalR 向前端推送图像
  • 隐私保护与联邦学习文献阅读
  • Java实习模拟面试|离散数学|概率论|金融英语|数据库实战|职业规划|期末冲刺|今日本科计科要闻速递:技术分享与学习指南 - 实践