记录一种维护进位的数位DP。

例题

简要题意

有 \(K\le 100\) 种面值分别为 \(\{a_i\}, S=\sum a_i\le 1000\) 的纸币，有几种方式付 \(N\le 10^{18}\) 元。

题解

令 \(c_i\) 表示我们选了多少次 \(a_i\) ，我们考虑从小到大确定 \(c_i\) 的二进制位，或者说按行确定 \(c_i\) 。

我们发现考虑完第 \(i\) 位后， \(0\sim i\) 位就已经确定下来了，于是可以依赖这个性质减少 dp 状态，令 \(f_{i,j}\) 表示考虑到了第 \(i\) 位，前 \(i\) 位已经确定且与 \(N\) 的前 \(i\) 位相同，往后面进了 \(j\) 的时候的方案数，转移显然，时间复杂度 \(O(KS\log N)\) 。

pesudocode

carry <- (zero-padding array of length 2S + 1)
carry[0] <- 1
while M != 0 do
  for i = 1 to K do
    for k = 2S - a_i to 0 do
      carry[k + a_i] <- carry[k + a_i] + carry[k]
    end for
  end for
  for k = 0 to 2S + 1:
    p = 2k + (N mod 2)
    if p < 2S + 1 then
      carry[k] <- carry[p]
    else 
      carry[k] <- 0
    end if
  end for
  M <- floor(M / 2)
return carry[0]

ARC156D Xor Sum 5

简要题意

给定长度为 \(N\le 1000\) 的序列 \(\{a_i\},a_i\le 1000\) 和一个整数 \(K\le 10^{12}\) ，求 \(\bigoplus_X\sum_{i=1}^KA_{X_i}\) ，其中 \(X\) 为长度为 \(K\) 的值域为 \([1,n]\) 的所有合法排列。

题解

令 \(c_i\) 表示 \(a_i\) 被选择了几次，要使这种选择方式有贡献，就必须有 \(\binom{K}{c_1,c_2,\cdots,c_n}\) 为奇数，则每个 \(c_i\) 在二进制下必须为 \(K\) 的子集。

一样令 \(f_{i,j}\) 表示考虑到了第 \(i\) 位，进位为 \(j\) 的时候的方案数，转移不难得到，在最后算贡献的时候把上述限制考虑进来即可。

Code

const int N = 3100;
int n, a[N], f[100][N]; ll K, ans;
signed main() {
    scanf("%d %lld", &n, &K);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    f[0][0] = 1;
    for(int i = 0; i < 60; i++) {
        if((K >> i & 1) == 0) {
            for(int j = 0; j < 2048; j++)
                f[i + 1][j >> 1] ^= f[i][j];
            continue;
        }
        for(int j = 0; j < 2048; j++) if(f[i][j])
            for(int k = 1; k <= n; k++)
                f[i + 1][(j >> 1) + a[k]] ^= 1;
    }
    for(int i = 1; i <= 60; i++)
        for(int j = 0; j < 2048; j++)
            if(f[i][j] && (j & 1) && (n % 2 == 1 || (K >> i) == 0))
                ans ^= 1ll << (i - 1);
    printf("%lld\n", ans);
    debug("time=%.4lfs\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
}

CF1290F Making Shapes

简要题意

给定 \(n\) 个向量，你需要按照如下方式画图：

初始点在 \((0,0)\)
选择一个向量，从当前点连向当前点加上这个向量得到的点
重复第二个操作，最后回到 \((0,0)\) 并停止。

这样你可以得到一个多边形，问有多少种画法使得得到一个凸多边形且最终的多边形可以被放到 \(m\times m\) 的矩形里。输出答案对 \(998244353\) 取模。

\(n\le 5, m\le 10^9,|x_i|,|y_i|\le 4\)

题解

凸包则对于每一个确定的选择方式，图的形状一定，方案唯一。显然必须满足以下限制：

\(\sum_{x_i>0}c_ix_i=\sum_{x_i<0}-c_ix_i\) 且 \(\sum_{y_i>0}c_iy_i=\sum_{y_i<0}-c_iy_i\)
\(\sum_{x_i>0}c_ix_i\le m\) 且 \(\sum_{y_i>0}c_iy_i \le m\)

设计状态 \(f_{i,px,py,nx,ny,x,y}\) 表示考虑到第 \(i\) 位， \(\sum_{x_i>0}c_ix_i\) 进位为 \(px\) ，当前 \(x\) 轴坐标的后 \(i\) 位是否大于 \(m\) 的后 \(i\) 位，其余类似。转移易得。

Code

constexpr int P = 998244353;
int n, m, F[40][32][32][32][32][2][2], x[10], y[10];
int chk(int i, int j, int k) { return i != j ? i > j : k; }
int f(int i, int px, int py, int nx, int ny, int x_, int y_) {
    if(i >= 30) return (vi){px, py, nx, ny, x_, y_} == (vi){0, 0, 0, 0, 0, 0};
    int &val = F[i][px][py][nx][ny][x_][y_];
    if(val != -1) return val; val = 0;
    for(int s = 0; s < 1 << n; s++) {
        int px_ = px, py_ = py, nx_ = nx, ny_ = ny;
        for(int j = 0; j < n; j++) if(s >> j & 1)
            x[j] > 0 ? px_ += x[j] : nx_ -= x[j],
            y[j] > 0 ? py_ += y[j] : ny_ -= y[j];
        if(px_ % 2 == nx_ % 2 && py_ % 2 == ny_ % 2)
            (val += f(i + 1, px_ >> 1, py_ >> 1, nx_ >> 1, ny_ >> 1,
                      chk(px_ & 1, m >> i & 1, x_), chk(py_ & 1, m >> i & 1, y_))) %= P;
    }
    return val;
}
signed main() {
    memset(F, 0xff, sizeof(F));
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &x[i], &y[i]);
    printf("%d\n", (f(0, 0, 0, 0, 0, 0, 0) - 1 + P) % P);
    debug("time=%.4lfs\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
}