NOIP模拟赛 十八

A.

神秘 DP 的神秘做法。

先考虑朴素 DP ，发现最短路是可以钦定的，具体的，设 \(1\) 到其最短路为 \(d\) ，则称其为第 \(d\) 层。

要求，每一层如果存在点，一定要向上一层连边，同层可以随便连边，非相邻层不可连边。

其中异或和只不过是状态里多设一维 0/1 的问题，以下略去。

记 \(f[d, i, k, j]\) 表示考虑完前 \(d\) 层，第 \(d\) 层有 \(k\) 个点，总共有 \(i\) 个点， \(j\) 条边的方案数。

转移枚举下一层选的点数 \(\Delta p\) 和连的边数 \(\Delta e\) ，提前预处理辅助数组，复杂度 \(O(n^8)\) 。

优化，没有必要同时枚举点数和边数的增量，可以将点依次填入，再决策边的连接。

对于 \(f[d, i, k, j]\) ，记 \(g[k, j]\) 表示下一层选了 \(k\) 个点，总共 \(j\) 条边的方案数。

（不定此层选了几条边是因为这样就可以不用卷积）

转移枚举选择了 \(t\) 条边，容斥得到式子 \(({k+k'\choose t} - {k'\choose t})\times g[k', j]\rightarrow g[k'+1,j+t]\) 。

再贡献给 \(f\) ，乘上重编号的系数。
复杂度 \(O(n^7)\) 。
（据说写的好看可以直接过）

点击查看

#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 = 50 + 1;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int n, m, a[LN], mod, C[LN * LN][LN * LN], ans[LN * LN];
int f[2][2][LN][LN][LN * LN], g[2][LN][LN * LN];bool ENDPOS;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; }int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> n >> mod; m = n * (n - 1) / 2;lep(i, 0, LN * LN - 1) { C[i][0] = 1;lep(j, 1, i) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);}lep(i, 0, n - 1) std::cin >> a[i];if (n == 1) {std::cout << a[0] << '\n';return 0;}int p = 0; f[p][a[0]][1][1][0] = 1;lep(d, 1, n - 1) {std::memset(f[p ^ 1], 0, sizeof(f[p ^ 1]));lep(i, 1, n) lep(k, 1, i) {std::memset(g, 0, sizeof(g));lep(j, 0, m)g[0][0][j] = f[p][0][i][k][j], g[1][0][j] = f[p][1][i][k][j];lep(dl, 1, n - i) {lep(j, 0, m) {lep(t, 1, k + dl - 1) if (j + t <= m) {upa(g[a[d]][dl][j + t], mul(C[k + dl - 1][t], g[0][dl - 1][j])),upa(g[a[d] ^ 1][dl][j + t], mul(C[k + dl - 1][t], g[1][dl - 1][j]));if (dl > t)upa(g[a[d]][dl][j + t], mod - mul(C[dl - 1][t], g[0][dl - 1][j])),upa(g[a[d] ^ 1][dl][j + t], mod - mul(C[dl - 1][t], g[1][dl - 1][j]));}}}lep(dl, 1, n - i) lep(j, 0, m) upa(f[p ^ 1][0][i + dl][dl][j], mul(C[i + dl - 1][dl], g[0][dl][j])),upa(f[p ^ 1][1][i + dl][dl][j], mul(C[i + dl - 1][dl], g[1][dl][j]));}p ^= 1;lep(k, 1, n) lep(j, n - 1, m)upa(ans[j], f[p][1][n][k][j]);}lep(i, n - 1, m) std::cout << (ans[i] + mod) % mod << ' ';std::cout << '\n';#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

考虑优化，我们将转移写成生成函数。

记 \(F_{i,k}=\sum_j f_{i,k,j}x^j\) ，\(G_k=\sum_j g_{k, j}x^j\) 。

则转移相当于 \(F_{i+k', k'} = F_{i, k}+{i+k'-1\choose k'}G_{k'}\) ，\(G_{k'+1}=G_{k'}((1+x)^k-1)(1+x)^{k'}\) 。

发现有很多 \(1+x\) ，我们维护 \(x\) 为占位符相当于把每个 \(1+x\) 又拆开了，很蠢。

直接定义 \(F_{i,k}=\sum_j f_{i,k,j}'(x+1)^j\) ，\(G_k=\sum_j g_{k, j}'(x+1)^j\) 。

那么转移就可以 \(O(1)\) 做了。

最后贡献的时候按照二项式定理拆开就好了。

复杂度 \(O(n^6)\) 。

点击查看

#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 = 50 + 1;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int n, m, a[LN], mod, C[LN * LN][LN * LN], ans[LN * LN];
int f[2][2][LN][LN][LN * LN], g[2][LN][LN * LN];bool ENDPOS;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; }int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> n >> mod; m = n * (n - 1) / 2;lep(i, 0, LN * LN - 1) { C[i][0] = 1;lep(j, 1, i) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);}lep(i, 0, n - 1) std::cin >> a[i];if (n == 1) {std::cout << a[0] << '\n';return 0;}int p = 0; f[p][a[0]][1][1][0] = 1;lep(d, 1, n - 1) {std::memset(f[p ^ 1], 0, sizeof(f[p ^ 1]));lep(i, 1, n) lep(k, 1, i) {std::memset(g, 0, sizeof(g));lep(j, 0, m)g[0][0][j] = f[p][0][i][k][j], g[1][0][j] = f[p][1][i][k][j];lep(dl, 1, n - i) {lep(j, 0, m) {upa(g[a[d]][dl][j + dl - 1], mod - g[0][dl - 1][j]);upa(g[a[d]][dl][j + dl + k - 1], g[0][dl - 1][j]);upa(g[a[d] ^ 1][dl][j + dl - 1], mod - g[1][dl - 1][j]);upa(g[a[d] ^ 1][dl][j + dl + k - 1], g[1][dl - 1][j]);}}lep(dl, 1, n - i) lep(j, 0, m) upa(f[p ^ 1][0][i + dl][dl][j], mul(C[i + dl - 1][dl], g[0][dl][j])),upa(f[p ^ 1][1][i + dl][dl][j], mul(C[i + dl - 1][dl], g[1][dl][j]));}p ^= 1;lep(k, 1, n) lep(j, n - 1, m) {rep(t, j, n - 1)upa(ans[t], mul(f[p][1][n][k][j], C[j][t]));}}lep(i, n - 1, m) std::cout << (ans[i] + mod) % mod << ' ';std::cout << '\n';#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

B.

容易发现操作 lowbit(n) 即可，不能这样操作则必败。

证明参考 Link （作者懒得证了，不保证引用文章正确）

C.

对序列求逆，变成排序问题。

定义两个基本操作，将 \(n\) 与 \(n-1\) 交换，将 \([1, n - 1]\) 向右循环一维。

这样我们就可以进行排序了。

具体的，如果 \(n\) 的位置是 \(n\) ，则随便找一个位置尚未确定的数放在 \(n\) 这个位置上。

否则，以 \(1\) 作为基准，直接将前面的序列循环移位若干次，使得交换之后末位数相对位置正确。

使用倍增加快这个过程，操作期望 \(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 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 = 2e5 + 7;
typedef long long ll;
typedef std::vector <int> vec ;
typedef std::pair<int, int> PII;const int M = 6;
vec jump[6]; int len[M + 1] = { 0, 1, 4, 16, 64, 256, 700 };
std::vector <vec> perm(int n) { std::vector <vec> ans;jump[0].resize(n);lep(i, 0, n - 1) jump[0][i] = i;std::swap(jump[0][n - 1], jump[0][n - 2]);int d = 0;lep(i, 1, M) {d = len[i]; if (d >= n) break;jump[i].resize(n), jump[i][n - 1] = n - 1;lep(k, 0, n - 2) jump[i][k] = (n - 1 + k - d) % (n - 1);}lep(i, 0, M) if (jump[i].size()) ans.emplace_back(jump[i]); else break;return ans;
}int t[2][LN], op, n, c[LN], ans[LN];
int cnt = 0; std::bitset <LN> st;
il void work(int p) {lep(i, 0, n - 1) t[op ^ 1][i] = t[op][jump[p][i]], c[t[op ^ 1][i]] = i;ans[cnt++] = p, op ^= 1;
}
vec cons(vec p) { cnt = op = 0; int x;n = p.size(), st.set(), st.reset(0);lep(i, 0, n - 1) c[i] = p[i], t[op][c[i]] = i;if (c[0] == n - 1) work(0);lep(i, 1, n - 2) {if (t[op][n - 1] == n - 1) {x = n - 2 - c[st._Find_first()], --i;rep(j, M, 1) lep(k, 0, 4) if (len[j] <= x) x -= len[j], work(j);work(0);} else {x = n - 2 - (c[0] + t[op][n - 1]) % (n - 1), st.reset(t[op][n - 1]);rep(j, M, 1) lep(k, 0, 4) if (len[j] <= x) x -= len[j], work(j);work(0);}}if (c[0] != n - 1) {x = n - 1 - c[0];rep(j, M, 1) lep(k, 0, 4) if (len[j] <= x) x -= len[j], work(j);}vec t(cnt); lep(i, 0, cnt - 1) t[i] = ans[i];return t;
}

D.

将有自环就无解判掉。

可以证明的是，颜色最多两种，\(u<v\) 和 \(u>v\) 各染一种就合法。

字典序考虑贪心，依次考虑边 \(u\rightarrow v\) ，如果 \(v\) 本来可以到 \(u\) ，将次边标记为 \(2\) ，否则加入这条边，标记为 \(1\) 。

正确性考虑一条边 \((u, v)\) 被染成 \(2\) ，那么在 \(1\) 组成的 DAG 上 \(u\) 的拓扑序大于 \(v\) ，所以 \(2\) 边组成的图仍然是 DAG。

如果维护连通性呢？很难维护就考虑上根号。

每 \(\sqrt n\) 次操作为一组，需要考虑 \(O(\sqrt n)\) 对边之间的可达性，提前 bitset 预处理。

直接模拟，加边就把所有的关键点扫描一遍更新。

复杂度 \(O(n\sqrt 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 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 = 1e5 + 7;
const int LM = 600 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int n, m, u[LN], v[LN], B, id[LN], stk[LN], tot;
std::bitset <LM> to[LN];
std::bitset <LN> ans, vis;
std::vector <int> e[LN];bool ENDPOS;void dfs(int u) {if (vis[u]) return; vis[u] = true;if (id[u]) to[u].set(id[u]);for (int v : e[u]) dfs(v), to[u] = to[u] | to[v];
}
void solve(int l, int r) { tot = 0;lep(i, l, r) {if (!id[u[i]]) id[u[i]] = ++tot, stk[tot] = u[i];if (!id[v[i]]) id[v[i]] = ++tot, stk[tot] = v[i];}lep(i, 1, n) if (id[i]) dfs(i);lep(i, l, r) {if (to[v[i]][id[u[i]]]) { ans.set(i); continue; }e[u[i]].push_back(v[i]);lep(j, 1, tot) if (to[stk[j]][id[u[i]]]) to[stk[j]] |= to[v[i]];}lep(i, 1, n) id[i] = 0, to[i].reset(); vis.reset();
}int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> n >> m; B = 300;lep(i, 1, m) {std::cin >> u[i] >> v[i];if (u[i] == v[i]) { std::cout << "-1\n"; return 0; }}int l = 0;lep(i, 1, m) if (i == m or i - l == B) solve(l + 1, i), l = i;lep(i, 1, m) std::cout << (ans[i] + 1) << ' ';std::cout << '\n';#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}