【题解】CF1290F Making Shapes | 20211215 模拟赛 图形【数位DP】
题目链接
题目链接
题意
有 \(n\) 个向量,每个向量重复若干遍,首位相接拼成凸包,要求其能被 \(m\times m\)、边界与坐标轴平行的正方形覆盖。问方案数。\(n\leq 5,|x|,|y|\leq 4,m\leq 10^9\)
题解
按照二进制位从低到高确定每个向量的个数。设 \(f_{i,px,nx,py,ny,gx,gy}\) 表示:
- 现在还有 \(i\) 个最低的二进制位没有确定;
- 正的横坐标之和要进位 \(px\);
- 负的横坐标之和要进位 \(nx\);
- 正的纵坐标之和要进位 \(py\);
- 负的纵坐标之和要进位 \(ny\);
- \(gx\):最后 \(i\) 位,横坐标之和是否超出 \(m\);
- \(gy\):最后 \(i\) 位,纵坐标之和是否超出 \(m\)。
转移时保持横坐标、纵坐标之和相等。初始状态为最高位时,后面六维都是 0 才返回 1。