T1
小鸣的疑惑
观察发现第一项贡献恒正，第二项贡献恒负，第三项贡献为 \(0\)，并且一项的贡献与后面无关。于是套用对第三项的分析会发现从第三项往后的所有东西贡献都是 \(0\)。于是答案为 \(a_1 - a_2\)。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
int n;
int a[100005];
signed main() {
freopen("aminusb.in", "r", stdin);
freopen("aminusb.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << (a[1] - a[2] + P) % P << "\n";
}
return 0;
}
T2
红蔷薇白玫瑰
dfs 枚举答案，只需要判断走到当前点的路径的后 \(m\) 位是否和给定串匹配即可。哈希或 kmp 自动机或 AC 自动机都能做。
代码
#include <iostream>
#define int long long
using namespace std;
const int B = 2333;
const int P = 1610612741;
int ls[300005], rs[300005], ans[300005];
int n, m, hm1, hm2, pw1, pw2;
unsigned long long h1[300005];
int h2[300005], stk[300005];
void dfs(int x, int d) {
stk[d] = x;
if (d > m) {
if (h1[d] - h1[d - m] * pw1 == hm1 && (h2[d] - h2[d - m] * pw2 % P + P) % P == hm2)
ans[stk[d - m]] = x;
}
if (ls[x]) {
h1[d + 1] = h1[d] * B + 1;
h2[d + 1] = (h2[d] * B + 1) % P;
dfs(ls[x], d + 1);
}
if (rs[x]) {
h1[d + 1] = h1[d] * B + 2;
h2[d + 1] = (h2[d] * B + 2) % P;
dfs(rs[x], d + 1);
}
}
signed main() {
freopen("rose.in", "r", stdin);
freopen("rose.out", "w", stdout);
cin >> n;
for (int i = 1; i < n; i++) {
int u, w, v;
cin >> u >> v >> w;
w ? (rs[u] = v) : (ls[u] = v);
}
cin >> m;
for (int i = pw1 = pw2 = 1, x; i <= m; i++) {
cin >> x;
hm1 = hm1 * B + x + 1;
hm2 = (hm2 * B + x + 1) % P;
pw1 = pw1 * B;
pw2 = pw2 * B % P;
}
dfs(1, 1);
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << "\n";
return 0;
}
T3
山遥路远
考虑判断括号串，第一种方法是从前往后扫并记录当前左括号个数。套到这个题一看就非常扯淡，因为你就算能知道左括号最多有多少这个做法所需要的 dp 的状态数也是不能在套了一个 dijkstra 之后通过的，没有前途。我们考虑区间 dp 判断括号串。设 \(f[x][y]\) 表示从 \(x\) 到 \(y\) 中间构成合法括号串的最小长度。然后转移只需要考虑把两个拼起来和在两边各拼一个。这个做法转移简单，状态数少，简直不能更有前途一点了。我们考虑直接在这个做法上套 dijkstra，每次取出堆顶的时候直接枚举在当前串后面拼的合法括号串是从 \(y\) 到哪个点，以及要从哪个点拼一个合法括号串到 \(x\)。对于前后各拼一个我们直接做分步转移，有辅助状态 \(g[x][y]\) 表示目前 \(x \rightarrow y\) 去掉第一个字符（左括号）就是合法括号序列的最小长度，然后两个 dp 用一个 dijkstra 一块转移就没了。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#define int long long
using namespace std;
const int P = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, qs;
int f[405][405], g[405][405];
bool vis[2][405][405];
struct node {
int t, x, y, dis;
};
vector<pair<int, int> > G1[405], G2[405];
inline bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
void dijkstra() {
for (int i = 1; i <= n; i++) q.push((node) { 0, i, i, f[i][i] = 0 });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.x, y = tmp.y, t = tmp.t;
if (vis[t][x][y])
continue;
vis[t][x][y] = 1;
if (t) {
for (auto p : G1[y]) {
int v = p.first;
if (f[x][v] > g[x][y] + p.second)
q.push((node) { 0, x, v, f[x][v] = g[x][y] + p.second });
}
} else {
for (auto p : G2[x]) {
int v = p.first;
if (g[v][y] > f[x][y] + p.second)
q.push((node) { 1, v, y, g[v][y] = f[x][y] + p.second });
}
for (int i = 1; i <= n; i++) {
if (f[x][i] > f[x][y] + f[y][i])
q.push((node) { 0, x, i, f[x][i] = f[x][y] + f[y][i] });
}
for (int i = 1; i <= n; i++) {
if (f[i][y] > f[x][y] + f[i][x])
q.push((node) { 0, i, y, f[i][y] = f[i][x] + f[x][y] });
}
}
}
}
signed main() {
freopen("distant.in", "r", stdin);
freopen("distant.out", "w", stdout);
memset(f, 63, sizeof f);
memset(g, 63, sizeof g);
cin >> n >> m >> qs;
for (int i = 1; i <= m; i++) {
int u, v, ww, t;
cin >> u >> v >> ww >> t;
(t & 1) ? G2[v].emplace_back(make_pair(u, ww)) : G1[u].emplace_back(make_pair(v, ww));
}
dijkstra();
for (int i = 1, s, t; i <= qs; i++) {
cin >> s >> t;
cout << (f[s][t] == inf ? -1 : f[s][t]) % P << "\n";
}
return 0;
}
T4
命运歧途
首先考虑以子集反演为基础的容斥，由于对于一个钦定的非法（间隔）位置集合，没有被钦定的（间隔）位置会将序列分成若干段。我们只关心段的数量，所以只需要考虑钦定了多少非法位置。注意到每一段中都是公差为 \(k\) 的等差数列，因此考虑按照模 \(k\) 的余数将所有数分组。由于每个等差数列可以是增的也可以是减的，所以每个长度不为 \(1\) 的段有两种方案。那么现在相当于我们有若干个组，每组是一个数列，要求出将所有数列分段，一共分出来 \(x\) 段的方案数。在组之间我们直接背包合并，则只需要求出将 \(i\) 个数分 \(j\) 段的方案数。这个是容易前缀和优化到 \(\mathcal{O}(n^2)\) 的。然后每次询问就直接背包合并，这个复杂度就是 \(\mathcal{O}(qn^2)\) 的。然后考虑优化，发现对于每个 \(k\) 我们分的组的大小是 \(\lfloor \frac{n}{K} \rfloor\) 和 \(\lfloor \frac{n}{K} \rfloor + 1\) ，而这个东西的取值只有根号种。因此对每个这个东西的取值计算，就分成根号个块。容易发现块内分出的两种的个数都是单调的，于是可以类似莫队维护两个单调的指针每次移动。然后使用暴力多项式乘除就可以做到 \(\mathcal{O}(n^{2.5})\)。这里的多项式除法由于被除式的最高次项的系数一定是 \(1\)，所以直接除即可。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
int n, q, P;
inline void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int pre[4005][4005];
int f[4005][4005]; // i numbers, j segments
int F[4005], G[4005];
int fac[4005], ans[4005];
void Add(int x, int deg) {
for (int i = 0; i <= deg; i++) G[i] = F[i];
for (int i = deg; ~i; i--) {
if (F[i]) {
for (int j = 1; j <= x; j++) {
if (f[x][j])
Madd(F[i + j], 1ll * F[i] * f[x][j] % P);
}
}
}
for (int i = 0; i <= deg; i++) Madd(F[i], P - G[i]);
}
void Del(int x, int deg) {
for (int i = deg, v; i >= x; i--) {
v = G[i - x] = F[i];
for (int j = 0; j <= x; j++)
Madd(F[i - j], P - 1ll * v * f[x][x - j] % P);
}
memset(F, 0, sizeof F);
for (int i = 0; i <= deg - x; i++) F[i] = G[i];
}
signed main() {
freopen("fate.in", "r", stdin);
freopen("fate.out", "w", stdout);
cin >> n >> q >> P;
fac[0] = f[0][0] = 1;
for (int i = 0; i <= n; i++) pre[0][i] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = 1ll * fac[i - 1] * i % P;
for (int j = f[i][i] = pre[i][i] = 1; j <= n; j++) {
f[i][j] = (pre[i - 1][j - 1] + (j > 1 ? pre[i - 1][j - 2] : 0)) % P;
pre[i][j] = (pre[i][j - 1] + f[i][j]) % P;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++)
swap(f[i][j], f[j][i]);
}
int cur = 0;
for (int K = 1, m1, m2, c1, c2; K <= n; K++) {
if (K == 1 || n / K != n / (K - 1)) {
m1 = n / K, m2 = n / K + 1;
c1 = K - n % K, c2 = n % K;
memset(F, 0, sizeof F);
F[cur = 0] = 1;
for (int i = 1; i <= c1; i++) Add(m1, cur += m1);
for (int i = 1; i <= c2; i++) Add(m2, cur += m2);
} else {
while (c1 > K - n % K) Del(m1, cur), cur -= m1, --c1;
while (c1 < K - n % K) Add(m1, cur), cur += m1, ++c1;
while (c2 < n % K) Add(m2, cur), cur += m2, ++c2;
while (c2 > n % K) Del(m2, cur), cur -= m2, --c2;
}
for (int i = 0; i < n; i++) i & 1 ? Madd(ans[K], P - 1ll * F[n - i] * fac[n - i] % P) : Madd(ans[K], 1ll * F[n - i] * fac[n - i] % P);
}
while (q--) {
int x;
cin >> x;
cout << ans[x] << "\n";
}
return 0;
}
前两题花的时间有点长，这是不好的。
T3 一直在想记录左括号数量的 dp，无法优化，后来想到正解却以为只能在 DAG 上做。不好评价了。
T4 一直没有把两边都不是非法位置的位置视为独立段，就一直不会 dp。唐了。
标签：20241108,int,4005,long,括号,405,include From： https://www.cnblogs.com/forgotmyhandle/p/18536040