没补完（1/3），动作还是太慢了
A - 只不过是长的领带 2 / Just Long Neckties 2
https://www.luogu.com.cn/problem/P11665
需要观察到，任意时刻 \(B\) 中不存在重复元素。把 \(B\) 压出来，令 \(f_{i,S}\) 表示选了 \(i\)，当前 \(B\) 为 \(S\) 是否可行，能够 \(O(n\cdot 2^V)\)。对于某个 \(S\)，只关心它最远能到达哪个 \(i\)，故令 \(f_S\) 记录之。对于每一个 \(S\)，都可以找到 \(f_S\) 后第一对 \(a_i,a_{i+1}\notin S\)，用其刷表。
发现『找 \(f_S\) 后第一对非法元素』是很慢的，考虑优化；对于每个 \(i\) 维护 \(p\) 在其后第一次出现的位置 \(x\)，对于每个 \(a_x=p\) 维护 \(x\) 后方 \(a_y=p,a_{y+1}=q\) 第一次出现的位置，相当于先找 \(p\) 再找 \((p,q)\)，就可以做到 \(O(V^2\cdot 2^V+n\cdot V)\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
int V = 0;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
V = std::max(V, a[i]--);
}
std::vector<std::vector<int> > tx(n + 1, std::vector<int> (V)), ty(n + 1, std::vector<int> (V));
std::vector<int> lp(V);
std::vector<std::vector<int> > lpq(V, std::vector<int> (V));
for (int i = n; ~i; --i) {
if (i && i != n)
lpq[a[i]][a[i + 1]] = i;
for (int j = 0; j < V; ++j) {
tx[i][j] = lp[j];
if (i != n)
ty[i][j] = lpq[a[i]][j];
}
if (i != 0)
lp[a[i]] = i;
}
int siz = 1 << V, res = 21;
std::vector<int> f(siz);
for (int i = 0; i < siz; ++i) {
std::vector<int> p0, p1;
for (int j = 0; j < V; ++j)
if ((i >> j) & 1)
p1.push_back(j);
else
p0.push_back(j);
int j = n;
for (auto p : p0)
if (tx[f[i]][p])
for (auto q : p0)
if (ty[tx[f[i]][p]][q])
j = std::min(j, ty[tx[f[i]][p]][q]);
if (j != n) {
f[i ^ (1 << a[j])] = std::max(f[i ^ (1 << a[j])], j);
f[i ^ (1 << a[j + 1])] = std::max(f[i ^ (1 << a[j + 1])], j + 1);
for (auto k : p1) {
f[i ^ (1 << k) ^ (1 << a[j])] = std::max(f[i ^ (1 << k) ^ (1 << a[j])], j);
f[i ^ (1 << k) ^ (1 << a[j + 1])] = std::max(f[i ^ (1 << k) ^ (1 << a[j + 1])], j + 1);
}
}
else
res = std::min(res, __builtin_popcount(i));
}
std::cout << res << '\n';
return 0;
}B - Cut and Reorder
https://atcoder.jp/contests/abc328/tasks/abc328_g
不妨先重排再修改，令 \(f_{i,S}\) 表示已经重排好新序列的前 \(i\) 个元素，对应原序列状态 \(S\) 的最小代价。枚举新区间容易转移。可以发现枚举 \(i,S\) 的实际复杂度为 \(O(2^n)\)（空间也可以这么优化），预处理之后总时间复杂度 \(O(n^2\cdot 2^n)\)，跑不满，可以通过。
#include <bits/stdc++.h>
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
long long c;
std::cin >> n >> c;
std::vector<long long> a(n), b(n);
for (int i = 0; i < n; ++i)
std::cin >> a[i];
for (int i = 0; i < n; ++i)
std::cin >> b[i];
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
brr p(n, arr(n));
crr g(n, brr(n, arr(n)));
for (int l = 0; l < n; ++l)
for (int r = l; r < n; ++r) {
for (int k = l; k <= r; ++k)
p[l][r] ^= (1 << k);
for (int R = r - l; R < n; ++R)
for (int L = R, j = r; j >= l; --L, --j)
g[l][r][R] += std::abs(b[L] - a[j]);
}
int siz = 1 << n;
std::vector<long long> f(siz, inf);
f[0] = 0ll;
for (int j = 1; j < siz; ++j) {
int i = __builtin_popcount(j) - 1;
for (int r = 0; r < n; ++r)
for (int l = r; ~l && ((j >> l) & 1); --l)
f[j] = std::min(f[j], f[j ^ p[l][r]] + g[l][r][i] + c);
}
std::cout << f[siz - 1] - c << '\n';
return 0;
}C - Electric Circuit
https://atcoder.jp/contests/abc321/tasks/abc321_g
很像无向图容斥？令 \(f_S\) 表示让 \(S\) 内部完成配对，可以不连通的方案数，那么当且仅当 \(S\) 内部点出、入度之和相等（记为 \(cnt\)）时，\(f_S\) 有值 \(cnt!\)。相似地，设 \(g_S\) 表示让 \(S\) 完成配对，成为一个连通块的方案数，得到 \(g_S=f_S-\sum\limits_{v\in S} f_{S\oplus v}\cdot g_v\)。让 \(v\) 必须包含 \(S\) 中编号最小的点就可以去重。
从贡献的角度出发，\(S\) 带来的贡献就是 \(g_S\cdot f_{U\oplus S}\)，其中 \(U\) 是全集。最后除以 \(M!\) 求出期望。
复杂度 \(O(3^n)\)。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> ci(n), co(n);
for (int i = 1, x; i <= m; ++i)
std::cin >> x, ++ci[x - 1];
for (int i = 1, x; i <= m; ++i)
std::cin >> x, ++co[x - 1];
std::vector<long long> fac(m + 1);
fac[0] = 1ll;
for (int i = 1; i <= m; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
int siz = 1 << n;
std::vector<long long> f(siz), g(siz);
for (int i = 1; i < siz; ++i) {
int si = 0, so = 0;
for (int j = 0; j < n; ++j)
if ((i >> j) & 1)
si += ci[j], so += co[j];
if (si == so)
f[i] = fac[si];
}
auto res(0ll);
for (int i = 1; i < siz; ++i) {
g[i] = f[i];
int mn = 0;
for (int j = 0; j < n; ++j)
if ((i >> j) & 1) {
mn = j;
break;
}
int s = i ^ (1 << mn);
(g[i] += mod - g[1 << mn] * f[s] % mod) %= mod;
for (int j = (s - 1) & s; j; j = (j - 1) & s)
(g[i] += mod - g[j ^ (1 << mn)] * f[s ^ j] % mod) %= mod;
if (i != siz - 1)
(res += g[i] * f[(siz - 1) ^ i]) %= mod;
else
(res += g[i]) %= mod;
}
std::cout << res * qkp(fac[m], mod - 2) % mod << '\n';
return 0;
}D - Count Grid 3-coloring
https://atcoder.jp/contests/abc379/tasks/abc379_g
轮廓线 DP。把每一列已经确定的最靠下的元素压起来，每行逐个确定即可。
发现有效状态中只能容许最多一对相邻相同元素，这样复杂度就能降下来了。注意特判 \(1\times 1\) 的情况。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::array<int, 15> p;
p[0] = 1;
for (int i = 1; i < 15; ++i)
p[i] = p[i - 1] * 3;
std::vector<std::vector<int> > a;
if (n >= m) {
a.assign(n + 1, std::vector<int> (m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
char t;
std::cin >> t, a[i][j] = (t == '?' ? -1 : t - '1');
}
}
else {
std::swap(n, m);
a.assign(n + 1, std::vector<int> (m + 1));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) {
char t;
std::cin >> t, a[j][i] = (t == '?' ? -1 : t - '1');
}
}
int siz = p[m];
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
std::vector<int> s, tab(siz, -1);
auto getv_1 = [&](int j, int i) {
return (j / p[i - 1]) % 3;
};
auto getv = [&](int j, int i) {
return (s[j] / p[i - 1]) % 3;
};
auto chg = [&](int j, int i, int v) {
return tab[s[j] - p[i - 1] * getv(j, i) + p[i - 1] * v];
};
auto out = [&](int i) {
std::string s;
for (int j = 1; j <= m; ++j)
s += '1' + getv_1(i, j);
return s.c_str();
};
for (int i = 0; i < siz; ++i) {
s.push_back(i);
int cnt = 0;
for (int j = 2; j <= m; ++j)
if (getv_1(i, j - 1) == getv_1(i, j) && ++cnt >= 2) {
s.pop_back();
break;
}
}
for (int i = 0; i < (int)s.size(); ++i)
tab[s[i]] = i;
siz = (int)s.size();
if (n == 1) {
std::cout << (a[1][1] == -1 ? 3 : 1) << '\n';
return 0;
}
crr f(n + 1, brr(m + 1, arr(siz)));
for (int i = 0; i < siz; ++i)
if ([&](int i, int s) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] != -1 && a[i][j] != getv(s, j))
return false;
if (j != 1 && getv(s, j) == getv(s, j - 1))
return false;
}
return true;
} (1, i)) {
for (int p = 0; p < 3; ++p)
if ((a[2][1] == -1 || a[2][1] == p) && getv(i, 1) != p && ~chg(i, 1, p))
(++f[2][1][chg(i, 1, p)]) %= mod;
}
for (int i = 2; i <= n; ++i) {
for (int k = 1; k < m; ++k)
for (int j = 0; j < siz; ++j)
if (f[i][k][j]) {
// printf("f[%d][%d][%s] = %lld\n", i, k, out(s[j]), f[i][k][j]);
for (int p = 0; p < 3; ++p)
if ((a[i][k + 1] == -1 || a[i][k + 1] == p) && getv(j, k) != p && getv(j, k + 1) != p && ~chg(j, k + 1, p))
(f[i][k + 1][chg(j, k + 1, p)] += f[i][k][j]) %= mod;
}
for (int j = 0; j < siz; ++j)
if (i != n && f[i][m][j])
for (int p = 0; p < 3; ++p)
if ((a[i + 1][1] == -1 || a[i + 1][1] == p) && getv(j, 1) != p && ~chg(j, 1, p))
(f[i + 1][1][chg(j, 1, p)] += f[i][m][j]) %= mod;
}
auto res = 0ll;
for (int i = 0; i < siz; ++i)
(res += f[n][m][i]) %= mod;
std::cout << res << '\n';
return 0;
}E - Pure Straight
https://atcoder.jp/contests/arc126/tasks/arc126_d
手玩发现只要最终序列确定，那么移动的顺序不影响答案。故考虑确定目标位置和移动序列。考虑绝对值的几何意义，不妨令目标子序列中元素集中到被选中位置的中间元素，此时的代价可以计算。用点二进制技巧和库函数可以 \(O(1)\) 算代价。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
int siz = 1 << k;
std::vector<int> a(n + 1), f(siz, 0x3f3f3f3f);
auto out = [&](int j) {
std::string s;
for (int i = 0; i < k; ++i)
s += ('0' + ((j >> i) & 1));
return s.c_str();
};
f[0] = 0;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i], --a[i];
for (int j = siz - 1; j >= 0; --j) {
if (!((j >> a[i]) & 1))
f[j | (1 << a[i])] = std::min(f[j | (1 << a[i])], f[j] + __builtin_popcount(j & (~((1 << a[i]) - 1))));
f[j] += std::min(__builtin_popcount(j), k - __builtin_popcount(j));
}
}
std::cout << f[siz - 1] << '\n';
return 0;
}F - 123 Set
https://atcoder.jp/contests/arc184/tasks/arc184_b
做过 集合选数（这个 trick 见过很多次了，应该不只这一道，但我想不起来了）很容易想到画一个表格或者 DAG 出来，其实都能做
对于表格左上角和 DAG 的源点，肯定是一个 \(x\)，其不是 \(2\) 或 \(3\) 的倍数。如果画表，横乘 3 竖乘 2，观察一下是包含了 \(1\sim n\) 恰好一次的很多个杨表（没什么用，提一嘴而已），考虑转化目标，发现是用一个不可旋转的倒 L 形骨牌可叠放地铺满异形表格，可以考虑轮廓线 DP
具体地，用 1 来表示拐角处，0 表示其他，叠放的时候 1 的优先级比 0 高，然后就可以做了。以 3 为行，悲观估计单个表格大概有 \(31\times 2^{19}\) 个状态，运算次数差不多 \(31\times 19\times 2^{19}\)；再发现长得一模一样的表格肯定方案数是一样的，如果把任意一个表格全部除以 \(x\)，就会得到 \(n=10^9\div x\) 时 \(1\) 为左上角的杨表，就是说长相只和 \(10^9\div x\) 的值有关，可以整除分块 😱 可预计的跑得非常不满，实践下来是可以过的（但是很慢）
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
auto calc = [&](int r) {
return r - r / 2 - r / 3 + r / 6;
};
auto dp = [&](int lim) {
if (lim == 1) {
// printf("lim = 1, ret 1");
return 1;
}
int n = 1, m = 1;
for (int k = 1; k * 2 <= lim; ++n, k *= 2);
for (int k = 1; k * 3 <= lim; ++m, k *= 3);
int siz = 1 << m;
std::vector<std::vector<std::vector<int> > > f(2, std::vector<std::vector<int> > (2, std::vector<int> (siz))), p(n + 1, std::vector<std::vector<int> > (m));
std::vector<std::vector<std::vector<std::pair<int, int> > > > t(2, std::vector<std::vector<std::pair<int, int> > > (2, std::vector<std::pair<int, int> > (siz))); // sb
auto upd = [&](int i, int k, int j, int v) {
if (t[i & 1][k & 1][j] != std::make_pair(i, k)) {
p[i][k].push_back(j);
t[i & 1][k & 1][j] = { i, k }, f[i & 1][k & 1][j] = v;
}
else
f[i & 1][k & 1][j] = std::min(f[i & 1][k & 1][j], v);
return;
};
auto chg = [&](int i, int j, int v) {
return i ^ (((i >> j) & 1) << j) ^ (v << j);
};
for (int i = 0; i < siz; ++i) {
bool flag = 0;
for (int j = 0; j < m; ++j)
if (((i >> j) & 1) || (j && ((i >> (j - 1)) & 1)));
else {
flag = 1;
break;
}
if (!flag)
upd(1, m - 1, i, __builtin_popcount(i));
}
for (int i = 2; i <= n; i++) {
int m1 = 1;
for (int x = (1 << (i - 1)); x * 3ll <= lim; ++m1, x *= 3);
int siz1 = 1 << m1;
for (auto j : p[i - 1][m - 1]) {
if (j & 1)
upd(i, 0, chg(j & (siz1 - 1), 0, 0), f[(i - 1) & 1][(m - 1) & 1][j]);
upd(i, 0, chg(j & (siz1 - 1), 0, 1), f[(i - 1) & 1][(m - 1) & 1][j] + 1);
}
m = m1, siz = siz1;
for (int k = 0; k < m - 1; ++k)
for (auto j : p[i][k]) {
if (((j >> k) & 1) || ((j >> (k + 1)) & 1))
upd(i, k + 1, chg(j, k + 1, 0), f[i & 1][k & 1][j]);
upd(i, k + 1, chg(j, k + 1, 1), f[i & 1][k & 1][j] + 1);
}
}
int res = 0x3f3f3f3f;
for (auto i : p[n][m - 1])
res = std::min(res, f[n & 1][(m - 1) & 1][i]);
return res;
};
int res = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
if (calc(r) - calc(l - 1))
res += (calc(r) - calc(l - 1)) * dp(n / l);
}
std::cout << res << '\n';
return 0;
}