AT_abc306_h Balance Scale 题解
Links
Description
有 \(N\) 个编号为 \(1,2,\dots,N\) 的砝码。有 \(M\) 次比较操作,每次比较砝码 \(A_{i}\) 和 \(B_{i}\),\(A_{i}\) 在左侧。
分为三种情况:
- 左边的砝码更重。
- 右边的砝码更重。
- 两边的砝码重量相同。
将每次比较的结果使用字符 ">"、"=" 或 "<" 记录下来,形成一个长度为 \(M\) 的字符串 \(S\)。求一共有多少种可能的\(S\)。答案对 \(998\,244\,353\) 取模。
Solution
考虑如何对一组确定的砝码判断是否可行,若 \(A_{i} < B_{i}\) 从 \(A_{i}\) 所在集合向 \(B_{i}\) 所在集合连边,若 \(A_{i} > B_{i}\) 从 \(B_{i}\) 所在集合向 \(A_{i}\) 所在集合连边,相等利用并查集合并。如果出现环了无解。
但每条边的方向不知道,考虑到数据范围很小,可以使用状压 dp 枚举一个独立集,表示初始度数为 \(0\) 的点。当我们删去其中度数为 \(0\) 的点时,仍满足条件,因此我们有转移状态:
\[dp_{i} = \sum_{s \subset i,s \neq \emptyset} dp_{i \setminus s} \]但这样是错误的,某个集合本身被计算了,但他同时会作为另一个集合的子集被计算。我们容斥掉这些情况即可,考虑集合被算的次数与集合大小有关,简单的推出下面正确的转移方程。
\[dp_{i} = \sum_{s \subset i,s \neq \emptyset} dp_{i \setminus s} \times {(−1)^{ \left ( \left |s \right |+1 \right )}} \]其中 \(\left |s \right |\) 表示集合 \(s\) 的元素个数。
Codes
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 410101
#define mo 998244353
void read(int &p)
{
int k = 1;
p = 0;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
{
k = -1;
}
c = getchar();
}
while(c >='0' && c <= '9')
{
p = p * 10 + c - '0';
c = getchar();
}
p *= k;
return ;
}
void write_(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
{
write_(x / 10);
}
putchar(x % 10 + '0');
}
void writesp(int x)
{
write_(x);
putchar(' ');
}
void writeln(int x)
{
write_(x);
puts("");
}
int n,m;
int fa[max_n],dp[max_n];
pair<int,int> edge[max_n];
int can[max_n];
int find(int x)
{
if(fa[x] == x)
{
return x;
}
return fa[x] = find(fa[x]);
}
void init()
{
for(int i = 1;i <= n;i++)
{
fa[i] = i;
}
}
int lowbit(int x)
{
return (-x) & x;
}
int popcount(int x)
{
int cnt = 0;
while(x)
{
++cnt;
x -= lowbit(x);
}
return cnt;
}
signed main()
{
read(n),read(m);
for(int i = 1;i <= m;i++)
{
read(edge[i].first),read(edge[i].second);
}
for(int i = 0;i < (1LL << n);i++)
{
can[i] = popcount(i);
init();
for(int j = 1;j <= m;j++)
{
// 两个点都在集合中
if((i & (1 << edge[j].first - 1)) && (i & (1 << edge[j].second - 1)))
{
// 合并
if(find(edge[j].first) != find(edge[j].second))
{
fa[find(edge[j].first)] = find(edge[j].second);
// 注意集合大小要减 1
--can[i];
}
}
}
}
dp[0] = 1;
for(int i = 1;i < (1 << n);i++)
{
for(int j = i;j;j = i &(j - 1))
{
if(can[j] & 1)
{
dp[i] += dp[i ^ j];
}
else
{
dp[i] += mo - dp[i ^ j];
}
(dp[i] += mo)%= mo;
}
}
writeln(dp[(1 << n) - 1]);
return 0;
}
标签:int,题解,void,abc306,砝码,max,集合,dp
From: https://www.cnblogs.com/yuhang-ren/p/17544470.html