题意
给定 \(n\) 个向量，长度为整数，不会平行，可以重复地用这些向量从 \((0,0)\) 开始围一个凸多边形，要求 \(x\) 和 \(y\) 的极差都在 \(m\) 之内，求本质不同多边形个数 \(\bmod998244353\) 。
\((1\le n\le5,0\le|x_i|,|y_i|\le4,1\le m\le10^9)\)
题解
由于这是一个凸包，如果把 \((0,0)\) 当成 \(y\) 坐标最小的那个点，向量均是按极角排序的，所以只要知道每个向量选定了多少次就对应了一个本质不同的多边形。
发现如果在向量比较少的情况下不合法了，较多的时候难以弥补（奇怪逻辑）……
从 \(m\) 来考虑，把 \(m\) 按每一位考虑，从低到高，用数位 DP 的思路来进行转移：
记录 \(x_i\) 为正为负的长度之和，显然对于每一位必须合法（即该位的正负大小一致）。
将剩到下一位的长度除以进制数即可，需要记录。同时以数位 DP 的套路记录前面是否取满。
分析一下复杂度：
位数×(上一位的长度)^4×4×转移常数。
这种东西显然在 \(2\) 进制下比较优并且能写……
\(4\) 次方是有 \(x,y\) 正，负 。长度大小：上一位最多来 \(20\) ，除以 \(2\) 为 \(10\) ，再考虑更前面的位，最多为 \(10+5+2+1\) 。
转移常数是枚举这一位选了哪些向量，并加上长度贡献， \(O(n2^n)\) 。
这东西完全跑不满，随便过。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=10,S=32,W=20,mod=998244353;
int n,m,a[N][2],f[S][W][W][W][W][2][2];
int dp(int d,int l1,int l2,int r1,int r2,int u1,int u2){
if(d>30) return !l1&&!l2&&!r1&&!r2&&!u1&&!u2;
int&s=f[d][l1][l2][r1][r2][u1][u2];
if(s!=-1) return s;s=0;
for(int i=0;i<(1<<n);i++){
int nl1=l1,nl2=l2,nr1=r1,nr2=r2;
for(int j=0;j<n;j++) if(i>>j&1){
if(a[j][0]>0) nl1+=a[j][0];else nl2-=a[j][0];
if(a[j][1]>0) nr1+=a[j][1];else nr2-=a[j][1];
}
if((nl1^nl2)%2||(nr1^nr2)%2) continue;
int d1=nl1&1,d2=nr1&1,v1=u1,v2=u2,dn=m>>d&1;
if(d1>dn) v1=1;if(d1<dn) v1=0;if(d2>dn) v2=1;if(d2<dn) v2=0;
(s+=dp(d+1,nl1/2,nl2/2,nr1/2,nr2/2,v1,v2))%=mod;
}
return s;
}
signed main(){
scanf("%d%d",&n,&m);memset(f,-1,sizeof(f));
for(int i=0;i<n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
printf("%d\n",(dp(0,0,0,0,0,0,0)+mod-1)%mod);
return 0;
}