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;
}