题解 CF1290F Making Shapes

· · 题解

Codeforces 题面传送门 & 洛谷题面传送门

数位 dp 好题。

首先，由于是凸包，一但向量集合确定，凸包的形态肯定就已经确定了。考虑什么样的向量集合能够组成符合条件的凸包，我们假设第 i 个向量选了 c_i 次。因为凸包是首尾相连的，所以必然有 \sum\limits_{i=1}^nc_ix_i=0,\sum\limits_{i=1}^nc_iy_i=0。上式也可写作 \sum\limits_{x_i>0}c_ix_i=\sum\limits_{x_i<0}c_i(-x_i),\sum\limits_{y_i>0}c_iy_i=\sum\limits_{y_i<0}c_i(-y_i)。其次，由于凸包能够被放到 m\times m 的矩形内，所以凸包横纵坐标的极差必须 \le m，以横坐标为例，还是因为原图是一个凸包，所以凸包的横坐标肯定是先涨一段，再跌到最低点，再涨到 0，因此横坐标的极差为 \sum\limits_{x_i<0}c_i(-x_i)，同理纵坐标的极差为 \sum\limits_{y_i<0}c_i(-y_i)，因此一组 \{c_1,c_2,\cdots,c_n\} 符合条件的充要条件是：

接下来思考怎样求符合条件的 \{c_1,c_2,\cdots,c_n\} 的个数。注意到 n 很小，值域也很小，因此考虑数位 DP，考虑从低到高逐位确定 c_i 每一位的值，记 dp_{d,px,py,nx,ny,p,q} 表示当前确定了最低的 d 位，当前为正的 x_i 的 \sum c_ix_i 产生了 px 的进位，当前为负的 x_i 的 \sum c_i(-x_i) 产生了 nx 的进位，当前为正的 y_i 的 \sum c_iy_i 产生了 py 的进位，当前为负的 x_i 的 \sum c_i(-y_i) 产生了 ny 的进位，当前 \sum\limits_{x_i>0} c_ix_i 的后 d 位是否 \le m 的后 d 位，当前 \sum\limits_{y_i>0} c_iy_i 的后 d 位是否 \le m 的后 d 位的符合条件的 \{c_i\} 的个数，转移就枚举这 n 个数第 d+1 位的值即可。

复杂度 20^4·2^5·\log m，可以通过。写成记忆化搜索的形式可能会跑得快一点。

总结：看到求 \sum\limits_{i=1}^na_ic_i=X 的 \{c_i\} 的组数，并且 n,a_i 都很小而 X 很大的题目可以想到数位 DP，类似的还有这个题。

const int MOD=998244353;
int n,m,x[7],y[7],dp[34][23][23][23][23][2][2];
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
int chk(int dm,int dn,int ori){
    if(dm^dn) return (dn<dm)?0:1;
    return ori;
}
int calc(int p,int ps_x,int ps_y,int ng_x,int ng_y,int xm,int ym){
    if(p==30) return (!ps_x&&!ps_y&&!ng_x&&!ng_y&&!xm&&!ym);
    if(~dp[p][ps_x][ps_y][ng_x][ng_y][xm][ym]) return dp[p][ps_x][ps_y][ng_x][ng_y][xm][ym];
    int d=m>>p&1;dp[p][ps_x][ps_y][ng_x][ng_y][xm][ym]=0;
    for(int s=0;s<(1<<n);s++){
        int tps_x=ps_x,tps_y=ps_y,tng_x=ng_x,tng_y=ng_y;
        for(int i=1;i<=n;i++) if(s>>(i-1)&1){
            (x[i]>0)?(tps_x+=x[i]):(tng_x-=x[i]);
            (y[i]>0)?(tps_y+=y[i]):(tng_y-=y[i]);
        } int d_px=tps_x&1,d_py=tps_y&1,d_nx=tng_x&1,d_ny=tng_y&1;
        if(d_px==d_nx&&d_py==d_ny)
            add(dp[p][ps_x][ps_y][ng_x][ng_y][xm][ym],
            calc(p+1,tps_x>>1,tps_y>>1,tng_x>>1,tng_y>>1,chk(d,d_px,xm),chk(d,d_py,ym)));
    } return dp[p][ps_x][ps_y][ng_x][ng_y][xm][ym];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",(calc(0,0,0,0,0,0,0)-1+MOD)%MOD);
    return 0;
}