ABC458

C. C Stands for Center

枚举 C 出现的位置

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;int main() {string s;cin >> s;int n = s.size();ll ans = 0;rep(i, n) if (s[i] == 'C') {ans += min(i+1, n-i);}cout << ans << '\n';return 0;
}

D. Chalkboard Median

对顶堆板子

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;int main() {int x, q;cin >> x >> q;priority_queue<int> ql;priority_queue<int, vector<int>, greater<int>> qr;rep(qi, q) {rep(i, 2) {int a;cin >> a;if (a < x) ql.push(a);else qr.push(a);}if (ql.size() < qr.size()) {ql.push(x);x = qr.top(); qr.pop();}if (ql.size() > qr.size()) {qr.push(x);x = ql.top(); ql.pop();}cout << x << '\n';}return 0;
}

E. Count 123

题目要求 \(|a_i - a_{i+1}| \le 1\)。对于数字 \(\{1, 2, 3\}\)，这意味着：

• \(1\) 和 \(3\) 绝对不能相邻（因为 \(|1-3|=2 > 1\)）。
• \(2\) 是“桥梁”：从 \(1\) 变到 \(3\)，或者从 \(3\) 变到 \(1\)，中间必须至少有一个 \(2\)。
• 相同数字可以连续出现，\(1\) 后面可以接 \(1\) 或 \(2\)，\(3\) 后面可以接 \(3\) 或 \(2\) 。

我们将序列看作是 \(1\) 的连续块和 \(3\) 的连续块交替排列，中间由 \(2\) 进行隔离。

定义块的数量

设 \(g\) 为 1-块和 3-块的总数。

• 如果要交替，形式如：\(1\dots1 \xrightarrow{2} 3\dots3 \xrightarrow{2} 1\dots1 \xrightarrow{2} 3\dots3 \dots\)
• 若总块数为 \(g\)，则 1-块和 3-块的数量大约各占一半。
• 分为两种起始情况：
  • 以 1-块开头。
  • 以 3-块开头。

组合计数步骤 (针对“以 1-块开头”的情况)

对于固定的总块数 \(g\)：

• 分配 1-块：将 \(a\) 个“1”分成 \(g_a\) 个非空块。方案数为 \(\binom{a-1}{g_a-1}\)。
• 分配 3-块：将 \(c\) 个“3”分成 \(g_c\) 个非空块。方案数为 \(\binom{c-1}{g_c-1}\)。
• 强制放置 2：在 \(g\) 个块之间有 \(g-1\) 个间隔。由于 \(1\) 和 \(3\) 不能相邻，这 \(g-1\) 个间隔每个位置必须至少放一个 \(2\) 。
• 分配剩余的 2：
  • 总共有 \(a + c\) 个数字（\(1\) 和 \(3\)），它们之间及两端共有 \(a + c + 1\) 个可插空的位点。
  • 我们已经用掉了 \(g-1\) 个“2”来填补必要的间隔。
  • 剩下的 \(b - (g-1)\) 个“2”可以随意放入这 \(a + c + 1\) 个位点中。
  • 方案数为：\(\binom{a+b+c-(g-1)}{a+c}\) 。

代码实现

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using mint = modint998244353;struct modinv {int n; vector<mint> d;modinv(): n(2), d({0,1}) {}mint operator()(int i) {while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;return d[i];}mint operator[](int i) const { return d[i];}
} invs;
struct modfact {int n; vector<mint> d;modfact(): n(2), d({1,1}) {}mint operator()(int i) {while (n <= i) d.push_back(d.back()*n), ++n;return d[i];}mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {int n; vector<mint> d;modfactinv(): n(2), d({1,1}) {}mint operator()(int i) {while (n <= i) d.push_back(d.back()*invs(n)), ++n;return d[i];}mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {if (n < k || k < 0) return 0;return facts(n)*ifacts(k)*ifacts(n-k);
}mint h(int k, int n) {return comb(n+k-1, k);
}int main() {int a, b, c;cin >> a >> b >> c;mint ans;rep(ac, 2) {for (int g = 2;; ++g) {int gc = g/2, ga = g-gc;if (a < ga or c < gc) break;if (b < g-1) break;mint now = h(a-ga, ga);now *= h(c-gc, gc);now *= h(b-(g-1), a+c+1);ans += now;}swap(a, c);}cout << ans.val() << '\n';return 0;
}

F. Critical Misread

构建 AC 自动机：

• 将所有禁止字符串 \(S_i\) 插入字典树。
• 标记每个禁止字符串的结尾节点为“不合法”状态。
• 构建失配指针。注意：如果一个节点的失配指针指向一个不合法节点，那么该节点本身也是不合法的（因为它包含了一个禁止字符串作为后缀）。
• 将 \(\text{Trie}\) 补全为 \(\text{DFA}\)（确定性有限自动机），使得每个节点对于 \(26\) 个字母都有明确的转移。

矩阵构造：

• 设 \(\text{AC}\) 自动机中共有 \(M\) 个合法节点。
• 构造一个 \(M \times M\) 的转移矩阵 \(T\)，其中 \(T_{i,j}\) 表示从合法节点 \(i\) 输入一个字符转移到合法节点 \(j\) 的路径数（即有多少个字符 \(c \in \{'a' \dots 'z'\}\) 使得 \(\text{next}(i, c) = j\)）。

矩阵快速幂：

• 初始状态是一个 \(1 \times M\) 的向量 \(V_0 = [1, 0, \dots, 0]\)（只有根节点为 \(1\)）。
• 长度为 \(N\) 的结果向量为 \(V_N = V_0 \times T^N\)。
• 最终答案即为 \(V_N\) 中所有元素之和。

注意到这里的字符串长度很小，其实也可以暴力构建自动机

代码实现

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using mint = modint998244353;struct Aho {bool inited;using MP = unordered_map<char, int>;vector<MP> to;vector<int> cnt, fail;Aho(): to(1), cnt(1) {}int add(const string& s) {int v = 0;for (char c : s) {if (!to[v].count(c)) {to[v][c] = to.size();to.push_back(MP());cnt.push_back(0);}v = to[v][c];}cnt[v]++;return v;}void init() {fail = vector<int>(to.size(), -1);queue<int> q;q.push(0);while (q.size()) {int v = q.front(); q.pop();for (auto [c, u] : to[v]) {fail[u] = (*this)(fail[v], c);cnt[u] += cnt[fail[u]];q.push(u);}}}int operator()(int v, char c) const {while (v != -1) {auto it = to[v].find(c);if (it != to[v].end()) return it->second;v = fail[v];}return 0;}int operator[](int v) const { return cnt[v]; }
};template<typename T>
struct Matrix {int h, w;vector<vector<T>> d;Matrix() {}Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}Matrix& unit() {assert(h == w);rep(i,h) d[i][i] = 1;return *this;}const vector<T>& operator[](int i) const { return d[i];}vector<T>& operator[](int i) { return d[i];}Matrix operator*(const Matrix& a) const {assert(w == a.h);Matrix r(h, a.w);rep(i,h)rep(k,w)rep(j,a.w) {r[i][j] += d[i][k]*a[k][j];}return r;}Matrix pow(long long t) const {assert(h == w);if (!t) return Matrix(h,h).unit();if (t == 1) return *this;Matrix r = pow(t>>1);r = r*r;if (t&1) r = r*(*this);return r;}
};int main() {int n, k;cin >> n >> k;Aho aho;rep(i, k) {string s;cin >> s;aho.add(s);}aho.init();int m = aho.to.size();Matrix<mint> a(m, m);rep(i, m) {rep(c, 26) {int j = aho(i, 'a'+c);if (aho[j] == 0) a[i][j] += 1; }}Matrix<mint> x(1, m);x[0][0] = 1;x = x*a.pow(n);mint ans;rep(i, m) ans += x[0][i];cout << ans.val() << '\n';return 0;
}