Atcoder泛做-2
ABL_F.Heights and Pairs
有$2N$个数$h_i$，两两分成一组，形成$N$个数对。问有多少种分组的方案使得每组中两个元素互不相同
$N\leq 50000, h_i\leq 100000$
计数问题可以先从集合的角度考虑。
题目最终所求为恰好有0组数存在相同的方案数，不妨设集合幂级数$f[S]$表示将$S$中相同的数放到一组的方案数，其中$S$是一个长度为$2N$的二进制串，所求即为$f[\phi]$。
考虑放宽限制，即向超集方向反演。设$g[S]=\sum_{S \subset T} f[T]$，根据反演公式有$f[S]=\sum_{S \subset T} (-1)^{|T|-|S|} g[T]$。
计算$g[S]$即为钦定若干组相同的数，剩下的数随意的方案。可以发现，反演的系数以及“剩下的数随意”的方案都和集合$S$实际长度有关，于是考虑用长度来压缩集合。
设$h[i]=\sum_{|S|=i} g[S]$，我们发现所有$g[S]$中随意的方案都是$\frac{(2N-2i)!}{(N-i)!2^{N-i}}$。提取这个公因数之后，$h[i]=L(i)*\frac{(2N-2i)!}{(N-i)!2^{N-i}}$，其中$L(i)$表示选出$i$对数相同的方案数。
似乎可以DP。
设$cnt[i]$为数值为$i$一共有多少个。我们对每种数值枚举其分出的数对$j$做决策，可以写出一个背包状DP。
考虑到数据范围过大，因此这个背包DP使用OGF来加速。
设$OGF(i) = \sum_{j=0}^{2j\leq cnt[i]} C_{cnt[i]}^{2j}\frac{(2j)!}{j!2^j}x^j$
由于$cnt[i]$的总和不超过$2n$，因此所有的OGF一共不超过$n$项。但是$i$的范围是$10^5$。
考虑用分治FFT加速，这样每一层计算的多项式总项数不超过$n$，一共$log_2 (max{h_i})$层。
最终根据反演公式得到$f[\phi]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
constexpr int N = 1e5;
int Main()
{
int n;
read(n);
std::vector<int> h(n + n + 1);
std::vector<int> cnt(N + 1);
for (int i = 1; i <= n + n; ++i)
read(h[i]), cnt[h[i]]++;
Combinatorics<modint> combinatorics(n + n + 1);
std::vector<modint> inv2(n + 1);
inv2[0] = 1;
inv2[1] = modint{1} / 2;
for (int i = 2; i <= n; ++i)
inv2[i] = inv2[i - 1] * inv2[1];
std::vector<Poly<modint>> F(N + 1);
auto all = [&](int x) -> modint
{
return combinatorics.fac[x + x] * combinatorics.invfac[x] * inv2[x];
};
for (int i = 0; i <= N; ++i)
{
auto &p = F[i];
p.a.assign(cnt[i] / 2 + 1, modint{0});
for (int j = 0; j <= cnt[i] / 2; ++j)
p[j] = combinatorics(cnt[i], j + j) * all(j);
}
auto solve = [&](auto &&self, int l, int r) -> Poly<modint>
{
if (l == r)
return F[l];
int mid = (l + r) >> 1;
Poly G = self(self, l, mid), H = self(self, mid + 1, r);
return G * H;
};
auto G = solve(solve, 0, N);
G.resize(n + 1);
modint phi = 0;
for (int i = 0; i <= n; ++i)
{
if (i % 2 == 0)
phi += G[i] * all(n - i);
else
phi -= G[i] * all(n - i);
}
printf("%d\n", phi);
return 0;
}
|
总结一下：炫酷反演魔术以及用长度“压缩”集合状态的技巧。实际上所谓的容斥以及容斥系数，不妨直接考虑用反演来做，对于我个人来说是更简单更清晰的。
APC001F.XOR Tree
一棵$N$个节点的无向树，有边权。每次可以选择一条路径，将整条路径上所有的边权都异或一个$x$。
请找到最小的使得所有边权为0的操作次数。
树上路径的边权异或操作，可以考虑转化边权为点权。因此路径上除了两端之外，一个点周围会有两条边被异或了同一个数，如果这个点的点权跟这两条边有关，那么相当于点权只有两端在变动。
那么我们新构造的点权，既要考虑到儿子的边，也要考虑到父亲的边，不妨设点权为所有边的异或和。
于是边权全为0的充要条件是点权全为0。
充分条件是显然的，必要条件的话我们从叶子开始往上推，这样儿子边全为0，那么父亲边也只能为0。
那么一次操作就变成了操作路径两端的点权。显然一开始我们可以把点权相同的若干点放到一起操作，这样每种点权最终至多剩下一个。
现在我们有若干非零点权（不超过15个），每种至多一个，问最少用几次操作可以使得他们都为0。
考虑有$k$个数，$a_1, …, a_k$，如果$a_1\oplus\cdots \oplus a^k=0$，那么我们可以用$k-1$次操作使他们全变成0。
所以这个问题变成了一个分组问题，把这些权值分成若干组，每组的收益是1，最大化收益。
因此用状压DP解决，总复杂度为$O(3^{15}+N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
int Main()
{
int n;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i < n; ++i)
{
int u, v, w;
read(u, v, w);
u++, v++;
a[u] ^= w, a[v] ^= w;
}
int ans = 0;
std::array<int, 16> cnt{};
for (int i = 1; i <= n; ++i)
cnt[a[i]]++;
for (int i = 1; i < 16; ++i)
ans += cnt[i] / 2, cnt[i] %= 2;
int all = 0;
for (int i = 1; i < 16; ++i)
if (cnt[i])
all |= (1 << i);
// printf("%d\n", all);
std::vector<int> dp(1 << 16);
for (uint mask = 1; mask < (1 << 16); ++mask)
{
dp[mask] = INF<int>;
if ((mask & all) != mask)
continue;
int sum = 0;
for (int i = 0; i < 16; ++i)
if (mask & (1 << i))
sum ^= i;
dp[mask] = sum == 0 ? std::popcount(mask) - 1 : INF<int>;
}
for (uint mask = 1; mask < (1 << 16); ++mask)
{
if ((mask & all) != mask)
continue;
for (int pmask = mask; pmask; pmask = (pmask - 1) & mask)
dp[mask] = std::min(dp[mask ^ pmask] + dp[pmask], dp[mask]);
}
ans += dp[all];
std::cout << ans << std::endl;
return 0;
}
|
总结一下：前半部分是相对来说有点套路的树上路径异或问题；然后到每种点权只有一个的时候，稍微有点不知所措，这个时候可以考虑用套路化不那么明显的算法尝试着去套，比如DP、网络流等等。
ABC400G.Patisserie ABC 3
有三个长度为$N$的数组$a,b,c$。现在选出$k$个匹配，$(i,j)$匹配的权值是$max(a_i+a_j,b_i+b_j,c_i+c_j)$。求$k$个匹配的最大权
首先这个匹配的权值是忽悠人的。因为总权值是加法，单个权值还是加法中取MAX，因此我们把MAX打开，这样相当于选出$2k$个数，每个数四种选法（不选，选$a$，选$b$，选$c$)，每种选出来的都得是偶数个。这样虽然统计了不合法的策略，但是最佳的策略一定合法且一定能被统计到。
考虑DP，$dp[i][k][mask]$表示前$i$个数，选出$k$个，目前$a,b,c$的数量奇偶性是$mask$的最大权值。转移是很简单的。
复杂度$O(NK)$
根据KM算法或者费用流我们可以知道最大权值匹配这个东西是个凸的。
不妨考虑Alien DP。因为选出$k$个匹配是凸的，利用Alien DP我们可以得到分一组额外扣除$mid$的权值，那么放到每个数上就是额外扣除$mid/2$的权值。
为了避免$mid/2$带来的浮点数，不妨考虑将权值双倍，这样单个数损失$mid$，但权值是$2a[i],2b[i],2c[i]$
这样总复杂度$O(Nlog_2N)$，有一个32的常数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
int Main()
{
int n, k;
std::cin >> n >> k;
std::vector<std::array<int, 3>> a(n + 1);
for (int i = 1; i <= n; ++i)
for (int p = 0; p < 3; ++p)
std::cin >> a[i][p];
// std::vector<std::array<std::pair<ll, int>, 8>> dp(n + 1);
auto DP = [&](auto mid)
{
std::vector<std::pair<ll, int>> dp(8), ndp(8);
std::fill(dp.begin(), dp.end(), std::pair{(ll)-1e18, 0});
dp[0] = {0, 0};
for (int i = 1; i <= n; ++i)
{
ndp = dp;
for (int mask = 0; mask <= 7; ++mask)
{
for (int p = 0; p < 3; ++p)
ndp[mask] = std::max(ndp[mask], {dp[mask ^ (1 << p)].first + 2 * a[i][p] - mid, dp[mask ^ (1 << p)].second + 1});
}
dp = ndp;
}
return dp[0];
};
ll l = -1e10, r = 1e10;
while (l <= r)
{
auto mid = (l + r) >> 1;
auto res = DP(mid);
if (res.second >= k + k)
l = mid + 1;
else
r = mid - 1;
}
// printf("%d\n", l - 1);
auto res = DP(l - 1);
auto ans = res.first + 1ll * (k + k) * (l - 1);
printf("%lld\n", ans >> 1);
return 0;
}
|