- 特此声明:该文章中的代码和解法均来自博主cup-pyy,我只是对其代码添加了详细注解,以及部分思路的详细化,原文链接见:这里
二维平面转为一维
注意我们最多含有22个坐标,但是实际上只会有21*21个格子 如何判断二维平面中的格子数量全部染黑?一维情况状态压缩十分容易,二维的情况将若干个一维拼接即可
bitset<500> t;
lop(i, 0, n)
{
r[i].a.x = lower_bound(xs + 1, xs + cntx + 1, r[i].a.x) - xs;
r[i].a.y = lower_bound(ys + 1, ys + cnty + 1, r[i].a.y) - ys;
r[i].b.x = lower_bound(xs + 1, xs + cntx + 1, r[i].b.x) - xs;
r[i].b.y = lower_bound(ys + 1, ys + cnty + 1, r[i].b.y) - ys;
mask[i].reset();
t.reset();
t = (1 << (r[i].b.y - r[i].a.y)) - 1;
t <<= r[i].a.y - 1;
lop(j, r[i].a.x - 1, r[i].b.x - 1)
{
mask[i] |= (t << (j * (cnty - 1)));
}
}
期望dp方程化简
设cnt 为状态i 中1 的数量
-
f
[
k
]
=
1
+
1
n
∑
i
=
0
n
f
[
k
∣
(
1
<
<
i
)
]
f[k]=1+\cfrac{1}{n}\sum_{i=0}^{n}f[k\mid(1<<i)]
f[k]=1+n1?∑i=0n?f[k∣(1<<i)],
1
1
1表示固定的染色步数花费
-
f
[
k
]
=
1
+
c
n
t
n
f
[
k
]
+
1
n
∑
(
k
&
(
1
<
<
i
)
)
=
=
0
f
[
k
∣
(
1
<
<
i
)
]
f[k]=1+\cfrac{cnt}{n}f[k]+\cfrac{1}{n}\sum_{(k\&(1<<i))==0}f[k|(1<<i)]
f[k]=1+ncnt?f[k]+n1?∑(k&(1<<i))==0?f[k∣(1<<i)]
-
n
?
c
n
t
n
f
[
k
]
=
1
+
1
n
∑
(
k
&
(
1
<
<
i
)
)
=
=
0
f
[
k
∣
(
1
<
<
i
)
]
\cfrac{n-cnt}{n}f[k]=1+\cfrac{1}{n}\sum_{(k\&(1<<i))==0}f[k|(1<<i)]
nn?cnt?f[k]=1+n1?∑(k&(1<<i))==0?f[k∣(1<<i)]
-
f
[
k
]
=
(
1
+
1
n
∑
(
k
&
(
1
<
<
i
)
)
=
=
0
f
[
k
∣
(
1
<
<
i
)
]
)
×
n
n
?
c
n
t
f[k]=(1+\cfrac{1}{n}\sum_{(k\&(1<<i))==0}f[k|(1<<i)])\times\cfrac{n}{n-cnt}
f[k]=(1+n1?∑(k&(1<<i))==0?f[k∣(1<<i)])×n?cntn?
完整的注释代码
#include <bits/stdc++.h>
using namespace std;
#define el '\n'
#define pb push_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
typedef long long LL;
typedef pair<int, int> PII;
struct read
{
static const int M = 1 << 21;
char buf[M], *S = buf, *P = buf, c, f;
inline char getc()
{
return (S == P && (P = (S = buf) + fread(buf, 1, 1 << 21, stdin), S == P) ? EOF : *S++);
}
template <typename T>
read &operator>>(T &x)
{
for (c = 0; !isdigit(c); c = getc())
f = c;
for (x = 0; isdigit(c); c = getc())
x = x * 10 + (c - '0');
return x = (f ^ '-') ? x : -x, *this;
}
} fin;
constexpr int N = 23, M = 2e6 + 10, B = 10, md = 998244353;
const double PI = acos(-1), eps = 1e-8;
int T, n, m;
int w, h, cntx, cnty;
int f[1 << B];
int xs[N], ys[N];
int fpow(int a, int b)
{
LL res = 1;
while (b)
{
if (b & 1)
res = res * a % md;
b >>= 1;
a = 1LL * a * a % md;
}
return res;
}
struct Rect
{
PII a, b;
} r[15];
int inv[N];
int k;
bitset<500> mask[10], state;
void dfs(int u, int s)
{
if(u == n)
{
f[s] = (state.count() == k) ? 0 : - 1;
return;
}
bitset<500> bk = state;
dfs(u + 1, s);
state = bk;
state |= mask[u];
dfs(u + 1, s | (1 << u));
return ;
}
int main()
{
rep(i, 1, 19)
{
inv[i] = fpow(i, md - 2);
}
fin >> T;
while (T--)
{
fin >> n >> w >> h;
cntx = cnty = 0;
lop(i, 0, n)
{
fin >> r[i].a.x >> r[i].a.y >> r[i].b.x >> r[i].b.y;
if (r[i].a.x > w)
r[i].a.x = w;
if (r[i].a.y > h)
r[i].a.y = h;
if (r[i].b.x > w)
r[i].b.x = w;
if (r[i].b.y > h)
r[i].b.y = h;
xs[++cntx] = r[i].a.x;
xs[++cntx] = r[i].b.x;
ys[++cnty] = r[i].a.y;
ys[++cnty] = r[i].b.y;
}
sort(xs + 1, xs + cntx + 1);
sort(ys + 1, ys + cnty + 1);
cntx = unique(xs + 1, xs + cntx + 1) - (xs + 1);
cnty = unique(ys + 1, ys + cnty + 1) - (ys + 1);
k = (cntx - 1) * (cnty - 1);
bitset<500> t;
lop(i, 0, n)
{
r[i].a.x = lower_bound(xs + 1, xs + cntx + 1, r[i].a.x) - xs;
r[i].a.y = lower_bound(ys + 1, ys + cnty + 1, r[i].a.y) - ys;
r[i].b.x = lower_bound(xs + 1, xs + cntx + 1, r[i].b.x) - xs;
r[i].b.y = lower_bound(ys + 1, ys + cnty + 1, r[i].b.y) - ys;
mask[i].reset();
t.reset();
t = (1 << (r[i].b.y - r[i].a.y)) - 1;
t <<= r[i].a.y - 1;
lop(j, r[i].a.x - 1, r[i].b.x - 1)
{
mask[i] |= (t << (j * (cnty - 1)));
}
}
state.reset();
dfs(0, 0);
if(f[(1 << n) - 1] == -1)
{
puts("-1");
continue;
}
dwn(i, (1 << n) - 1, 0)
{
if(f[i] != -1)
continue;
int cnt = 0, res = 0;
lop(j, 0, n)
{
if(i >> j & 1)
cnt ++;
else
res = (res + 1LL * inv[n] * f[i | (1 << j)]) % md;
}
f[i] = (1LL + res) * n % md * inv[n - cnt] % md;
}
cout << f[0] << el;
}
}
|