Solution -「CF 1290F」Making Shapes
\(\mathscr{Description}\)
??给定平面向量集 \(\newcommand{\vct}[1]{\boldsymbol{#1}}\{\vct v_n\}\),求从 \((0,0)\) 开始用这些向量作为方向画线段,求能画出的本质不同的封闭凸多边形,满足面积非 \(0\),且在 \(x\) 轴和 \(y\) 轴上的投影长度都不超过 \(m\)。答案对 \(998244353\) 取模。
??\(n\le 5\),向量集任意分量在 \([-4,4]\),\(m\le10^9\),此外所有数据都是整数。
\(\mathscr{Solution}\)
??出题人去为文惠君解牛吧!
??抽象一下要求,问题等价与求
\[\begin{cases} \sum_i c_ix_i=0\\ \sum_i c_iy_i=0\\ \sum_{x_i>0} c_ix_i\le m\\ \sum_{y_i>0} c_iy_i\le m \end{cases} \]中 \(\{c_n\}\) 的非负整数解数量。这什么玩意儿?类欧?半平面交?同余最短路?直接解离大谱了属于是。
??好,出题人开发了(或者搬运了)一个极其神奇的 trick:你不是要 \(\sum_ic_ix_i=0\) 吗?由于 \(x_i\) 很小,所以 每次加法对 bit 的改变有局限,那么,我们,数位 DP!
??由于正负混杂不方便,我们记 \(\textit{pxs}\) 表示正的 \(x\) 之和,\(\textit{nxs}\) 表示负的 \(x\) 之和;\(\textit{pys}\) 和 \(\textit{nys}\) 同理。从这个基本事实入手:确定了 \(c\) 的所有最低位之后,四个值的奇偶性(最低位)是确定的。这意味这若现在就有 \(\textit{pxs}\) 和 \(\textit{nxs}\) 的最低位不同,那么不管 \(c\) 怎么取,\(\textit{pxs}\neq\textit{nxs}\),联系限制,这种情况可以舍弃。
??推而广之,确定了 \(c\) 的所有低 \(i\) 位之后,四个值的低 \(i\) 位也都是确定的。这个时候,对于前两个限制,只需要记录 \(\textit{pxs}\) 等值除掉低 \(i\) 位的数值即可进行后续判断;后两个限制直接维护低 \(i\) 位是否有 \(\sum_{x_i>0}c_i^{(0..i-1)}x_i\le m^{(0..i-1)}\) 以及 \(y\) 对应的式子即可。因此,我们得到这样一个状态:
??令 \(f(i,\textit{pxs},\textit{nxs},\textit{pys},\textit{nys},0/1,0/1)\) 表示考虑了 \(c\) 的低 \(i\) 位,取到了这四个值,分别是否 \(\le m^{(0..i-1)}\)。转移时,只需要确定所有 \(c\) 的第 \(i+1\) 位,本质上是在取 \(\{\vct v_n\}\) 的子集,所以预处理出每个子集对四个值的贡献,就能做到 \(\mathcal O(\log m\cdot(nx)^4\cdot2\cdot2\cdot2^n)\) 转移。
\(\mathscr{Code}\)
/*+Rainybunny+*/
#include
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
const int MAXN = 5, MAXX = 4, MAXS = 1 << MAXN, MOD = 998244353;
int n, m, x[MAXN], y[MAXN];
int px[MAXS], py[MAXS], nx[MAXS], ny[MAXS];
int f[2][MAXN * MAXX + 1][MAXN * MAXX + 1]
[MAXN * MAXX + 1][MAXN * MAXX + 1][2][2];
inline void addeq(int& u, const int v) { (u += v) >= MOD && (u -= MOD); }
int main() {
// freopen("shape.in", "r", stdin);
// freopen("shape.out", "w", stdout);
scanf("%d %d", &n, &m);
rep (i, 0, n - 1) scanf("%d %d", &x[i], &y[i]);
rep (S, 0, (1 << n) - 1) {
rep (i, 0, n - 1) if (S >> i & 1) {
if (x[i] > 0) px[S] += x[i];
else nx[S] -= x[i];
if (y[i] > 0) py[S] += y[i];
else ny[S] -= y[i];
}
}
f[0][0][0][0][0][0][0] = 1;
int sta = 0;
rep (i, 0, 31 - __builtin_clz(m)) {
int mi = m >> i & 1;
rep (spx, 0, n << 2) rep (snx, 0, n << 2)
rep (spy, 0, n << 2) rep (sny, 0, n << 2) {
rep (upx, 0, 1) rep (upy, 0, 1) {
int& cur = f[sta][spx][snx][spy][sny][upx][upy];
if (!cur) continue;
rep (S, 0, (1 << n) - 1) {
int tpx = spx + px[S], tnx = snx + nx[S];
int tpy = spy + py[S], tny = sny + ny[S];
if ((tpx ^ tnx) & 1 || (tpy ^ tny) & 1) continue;
addeq(f[!sta][tpx >> 1][tnx >> 1][tpy >> 1][tny >> 1]
[(tpx & 1) != mi ? tpx & 1 : upx]
[(tpy & 1) != mi ? tpy & 1 : upy], cur);
}
cur = 0;
}
}
sta ^= 1;
}
printf("%d\n", (f[sta][0][0][0][0][0][0] + MOD - 1) % MOD);
return 0;
}