C. Between P and Q
暴搜
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;int main() {int n;cin >> n;vector<int> p(n), q(n), a(n);rep(i, n) cin >> p[i];rep(i, n) cin >> q[i];rep(i, n) a[i] = i+1;int ans = 0;do {if (p < a and a < q) ++ans;} while (next_permutation(a.begin(), a.end()));cout << ans << '\n';return 0;
}
D. Pre-Palindrome
对每个回文中心做中心扩展
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;int main() {string s;cin >> s;int n = s.size();int ans = 0;rep(p, 2) {rep(sl, n-p) {int l = sl, r = sl+p, cnt = 0;while (0 <= l and r < n) {if (s[l] != s[r]) ++cnt;if (cnt > 1) break;++ans;--l; ++r;}}}cout << ans << '\n';return 0;
}
E. Sum of Average
要求的是所有连续子数组平均值的和：$$S = \sum_{1 \le l \le r \le N} \frac{\sum_{m=l}^r A_m}{r - l + 1}$$如果把长度倒数设为序列 \(B\)，其中 \(B_k = \frac{1}{k+1}\)，那么原式本质上是：每一个元素 \(A_j\) 与每一个长度倒数 \(B_k\) 乘积的组合累加。
对于固定的 \(A_j\) 和固定的长度倒数 \(B_k\)，包含 \(A_j\) 且长度为 \(k+1\) 的子数组有多少个？
经过简单的边界推导，满足条件的子数组个数为：$$c(j, k) = \min(j + 1, N - j, k + 1, N - k)$$
因此，要求的总和可以写成：$$S = \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} A_j \cdot B_k \cdot \min(j + 1, N - j, k + 1, N - k)$$
观察系数 \(c(j, k) = \min(j + 1, N - j, k + 1, N - k)\)，可以将四项 \(\min\) 拆分为两组：
- \(\min(j + 1, N - j)\) 是位置 \(j\) 距离数组两端的较小距离（加 1）。
- \(\min(k + 1, N - k)\) 是长度 \(k\) 距离两端的较小距离（加 1）。
设 \(c(j, k) = M\)，意味着存在 \(M\) 个层级 \(i\)（\(0 \le i < M\)），使得：
- \(i \le \min(j, N - 1 - j)\) \(\iff\) \(j \in [i, N - 1 - i]\)
- \(i \le \min(k, N - 1 - k)\) \(\iff\) \(k \in [i, N - 1 - i]\)
换句话说，我们可以按区间剥离的“层级 \(i\)”来交换求和顺序：$$S = \sum_{i=0}^{\lfloor (N-1)/2 \rfloor} \left( \sum_{j=i}^{N-1-i} A_j \right) \left( \sum_{k=i}^{N-1-i} B_k \right)$$
然后预处理以下 \(A\) 和 \(B\) 的前缀和即可
更形象的可以看下面这张图：
可以发现，对于第一层，整个矩阵都填上了 \(1\)；对于第二层，往里缩一圈的矩阵继续填上 \(1\)，\(\cdots\)
代码实现
#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;int main() {int n;cin >> n;vector<int> a(n);rep(i, n) cin >> a[i];vector<mint> b(n);rep(i, n) b[i] = mint(i+1).inv();vector<mint> sa(n+1), sb(n+1);rep(i, n) sa[i+1] = sa[i]+a[i];rep(i, n) sb[i+1] = sb[i]+b[i];mint ans;for (int l = 0, r = n; l < r; ++l, --r) {ans += (sa[r]-sa[l])*(sb[r]-sb[l]);}cout << ans.val() << '\n';return 0;
}
F. Chmax
固定 \(x\) 的位置，然后求剩余数的 \(\text{LIS}\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;int main() {int n;cin >> n;vector<int> p(n);rep(i, n) cin >> p[i];int ans = 0;int mx = 0, lis = 0;const int INF = 1001001001;vector<int> dp(n, INF);rep(i, n) {if (mx < p[i]) {mx = p[i];ans++;}else {int j = lower_bound(dp.begin(), dp.end(), p[i]) - dp.begin();lis = max(lis, j+1);dp[j] = p[i];}}ans += lis;cout << ans << '\n';return 0;
}
G. Restricted Permutation
首先，根据题意可知 \(S\) 的首尾必须都是 o 才有解
注意到相邻两个 o 分隔出的不同段的填充方式是相互独立的，所以可以单独求每一段的填充方案数，然后乘起来就是答案
对于每一段的填充方案数可以用 \(\text{dp}\) + 简单容斥解决
代码实现
#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;mint f(int w) {vector<mint> facs(w+2, 1);rep(i, w+1) facs[i+1] = facs[i]*(i+1);vector<mint> dp(w);rep(i, w) {dp[i] = facs[i+2];rep(j, i) dp[i] -= dp[j]*facs[i-j+1];}return dp[w-1];
}int main() {int n;string s;cin >> n >> s;mint ans = 1;if (s[0] != 'o' or s[n-1] != 'o') ans = 0;else {int w = 0;for (int i = 1; i < n; ++i) {w++;if (s[i] == 'o') ans *= f(w), w = 0;}}cout << ans.val() << '\n';return 0;
}