题解：AT_abc436_g [ABC436G] Linear Inequation
ChatSheep
·
·
题解
题解
初步解法
因此我们考虑选择一个大于 $1$ 的整数 $B$，并把 $x_i$ 和 $M$ 给做一个进制转换，那么我们的条件就变成了这样：
$$\sum_{d\ge0}^{}B^d\sum_{i=1}^{N} (\lfloor{\frac{x_i}{B^d}}\rfloor\bmod B) A_i \le \sum_{d\ge0}^{}B^d(\lfloor{\frac{M}{B^d}}\rfloor\bmod B)$$
这就相当于有 $N$ 个 $B$ 进制的乘法竖式，其中乘数是确定的（即 $A_i$），你需要做的就是问有多少种同时确定被乘数的方案，使得最后的乘法运算结果的总和小于等于 $M$。
我们就可以发现这个数位 DP 就很明显了，只需要知道每一个 $d$ 所对应的 $\displaystyle(\lfloor{\frac{x_i}{B^d}}\rfloor\bmod B) A_i$ 即可，而且也可以快速处理到下一位的进位，因为进位的总量是不超过 $(B-1)\sum A_i$ 的，而且我们不需要关心竖式每一个数字填了什么，我们只需要关心他们的总和即可，这完全可以塞进去一个 DP 状态里面。
因此，我们考虑从低位到高位 DP，设状态 $\operatorname{dp}(d, jw, lim)$ 表示已处理完低 $d$ 位（即第 $0$ 到 $d-1$ 位），此时向第 $d$ 位的进位值为 $jw$，且已处理部分与 $M$ 的低 $d$ 位的大小关系为 $lim$。
这里，我们用 $lim=0$ 表示小于 $M$，用 $lim=1$ 表示等于 $M$，$lim=2$ 表示大于 $M$。这样，可以接受的状态就是 $jw=0,lim\le 1$。
我们再来思考一下具体的转移，转移显然是直接枚举 $\displaystyle\sum_{i=1}^{N} (\lfloor{\frac{x_i}{B^d}}\rfloor\bmod B) A_i$ 的值，假设这个值是 $jw'$，那么我们就可以转移到 $\operatorname{dp}(d+1,\lfloor\dfrac{jw'+jw}{B}\rfloor, lim')$。
对于 $lim'$ 的求解，这个是好做的，如果当前位 $(jw'+jw)\bmod B$ 等于 $\displaystyle\lfloor{\frac{M}{B^d}}\rfloor \bmod B$ 那么 $lim'=lim$，如果大于那么 $lim'=2$，否则就是 $lim'=0$。
不过显然这个还是要有一些转移系数，我们令 $\operatorname{cnt}(i)$ 为满足以下所有条件的 $(x_1,x_2,x_3,\dots,x_N)$ 的个数：
- $x_i< B$。
- $\displaystyle\sum x_iA_i=i$。
显然直接 $O(nB\sum A_i)$ 的大力背包是可以做的，这个非常简单，此处不赘述。
这样，我们最终的转移式子也就出来了：
$$\operatorname{dp}(d,jw,lim)=\sum_{jw'=0}^{\sum A_i} \operatorname{dp}(d+1,\lfloor\dfrac{jw'+jw}{B}\rfloor,lim')\times \operatorname{cnt}(jw')$$
其中：
$$lim'=\left\{\begin{aligned} 2 \space ((jw'+jw)\bmod B > (\lfloor{\frac{M}{B^d}}\rfloor\bmod B)) \\ lim \space ((jw'+jw)\bmod B = (\lfloor{\frac{M}{B^d}}\rfloor\bmod B)) \\ 0 \space ((jw'+jw)\bmod B < (\lfloor{\frac{M}{B^d}}\rfloor\bmod B))\end{aligned}\right.$$
（即数位 DP 的标记转移）。
边界条件定义为 $\displaystyle\operatorname{dp}(\lceil\log_B M\rceil+1, 0, 0/1)=1$。
这样我们得到了一个 $O(\log_B M \times (\sum A_i)^2 + (nB\sum A_i))$ 的做法。
参考代码如下：
:::info[代码]
```cpp
int dfs2(int i, int m) { // cnt[x] = dfs2(1, x)
if (i == n + 1) return m == 0;
if (dp2[i][m] != -1) return dp2[i][m];
int ans = 0;
for (int j = 0; j * a[i] <= m && j < B; ++j) {
ans += dfs2(i + 1, m - j * a[i]);
}
return dp2[i][m] = ans % p;
}
int dfs(int i, int jw, int lim) {
if (i == D) return lim <= 1 && jw == 0;
if (dp[i][jw][lim] != -1) return dp[i][jw][lim];
int ans = 0;
for (int njw = 0; njw <= n * 100; ++njw) {
int nowdig = (njw + jw) % B;
ans += dfs(i + 1, (njw + jw) / B, (nowdig > digs[i] ? 2 : (nowdig < digs[i] ? 0 : lim))) * dfs2(1, njw) % p;
}
return dp[i][jw][lim] = ans % p;
}
```
:::
### 转化
为了方便后续方便优化，我们不妨直接让 $B=2$，即直接在二进制下求解，这样就能方便奇偶性便于分离，对于其他的 $B$ 只会增加分类的数量，效率优化不明显。
然后我们发现这个式子实在是太过于繁琐了，于是我们考虑直接按照 $jw'+jw$ 的奇偶性进行分类讨论。
$$\operatorname{dp}(d,jw,lim)=\sum_{jw'=0}^{\sum A_i}[2\mid (jw'+jw)] \operatorname{dp}(d+1,\lfloor\dfrac{jw'+jw}{B}\rfloor,lim')\times \operatorname{cnt}(jw')\\ + \sum_{jw'=0}^{\sum A_i}[2\nmid( jw'+jw)] \operatorname{dp}(d+1,\lfloor\dfrac{jw'+jw}{B}\rfloor,lim')\times \operatorname{cnt}(jw')$$
这样做有很多好处，$\lfloor\dfrac{jw'+jw}{B}\rfloor$ 和 $(jw'+jw)\bmod B$ 我们都可以很方便地表示出来，因此不妨假设在 $(jw'+jw)\bmod B=1$ 的时候的新标记为 $lim_1$，另一种情况的标记是 $lim_0$。式子就可以变成这个样子：
$$\operatorname{dp}(d,jw,lim)=\sum_{jw'=0}^{\sum A_i}[2\mid (jw'+jw)] \operatorname{dp}(d+1,\dfrac{jw'+jw}{B},lim_0)\times \operatorname{cnt}(jw')\\ + \sum_{jw'=0}^{\sum A_i}[2\nmid( jw'+jw)] \operatorname{dp}(d+1,\dfrac{jw'+jw+1}{B},lim_1)\times \operatorname{cnt}(jw')$$
然后分别对两个和式进行换元，只需要把艾弗森括号消除掉即可。
$$\operatorname{dp}(d,jw,lim)=\sum_{jw'=0}^{\frac{\sum A_i}{2}}\operatorname{dp}(d+1,jw'+\lceil \frac{jw}{2} \rceil,lim_0)\times \operatorname{cnt}(jw'\times2+(jw\bmod2))\\ + \sum_{jw'=0}^{\frac{\sum A_i}{2}}\operatorname{dp}(d+1,jw'+\lfloor \frac{jw}{2} \rfloor,lim_1)\times \operatorname{cnt}(jw'\times2+1-(jw\bmod2))$$
### 卷积
我们首先让 $\operatorname{cnt_0}(x)=\operatorname{cnt}(x\times 2)$，$\operatorname{cnt_1}(x)=\operatorname{cnt}(x\times 2 + 1)$，后续转化就能变得好看一点。
容易发现，对于固定的 $(d,par, lim)$（其中中间的 $par$ 表示 $jw\bmod 2$，也就是 $jw$ 的奇偶性），我们都需要计算下面这个东西：
$$f_t = \sum_{k=0}^{\frac{\sum A_i}{2}}\operatorname{cnt}_{par}(k)\operatorname{dp}(d+1, k+t, lim)$$
注意我们需要求解所有的 $f_t$ 的结果，而 $t$ 的取值对应到上文就是 $\lfloor \dfrac{jw}{2}\rfloor$（奇数部分）或者是 $\lceil\dfrac{jw}{2}\rceil$（偶数部分）。对于每一个求解是耗费时间的，考虑用卷积优化，先将其转化成简单的形式。
不过很可惜 $k+k+t$ 并不是一个定值，我们考虑令 $\operatorname{cnt}'_{par}(k)=\operatorname{cnt}_{par}(\frac{\sum A_i}{2}-k)$，即直接把整个序列颠倒过来。那么式子就可以变成这样：
$$f_t = \sum_{k=0}^{\frac{\sum A_i}{2}}\operatorname{cnt}'_{par}(\frac{\sum A_i}{2}-k)\operatorname{dp}(d+1, k+t, lim)$$
然后再给 $k$ 换个元：
$$f_t = \sum_{k=0}^{\frac{\sum A_i}{2}}\operatorname{cnt}'_{par}(k)\operatorname{dp}(d+1, \frac{\sum A_i}{2}+t-k, lim)$$
于是：
$$a(k) = \operatorname{cnt}'_{par}(k)\\
b(k) = \operatorname{dp}(d+1, k, lim)\\
f_t =(a * b)\left[\frac{\sum A_i}{2} + t\right]$$
然后就可以直接卷积了。
时间复杂度 $O((n\sum A_i) \log (n\sum A_i)\log M)$，除去卷积带来的额外开销，有 $6$ 倍常数（$jw$ 的奇偶性和数位 DP 的标记个数）。
### 代码
这里卷积实现用的是 AC 库。
```cpp
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define int long long
const int B = 2, D = 62, V = 10000; // D > log M, V >= \sum A_i
int n, m, a[103], dp[D+1][V+2][3], dp2[101][V+2];
// dp[d][jw][lim] 与题解阐述的相同，d 表示当前位（从小到大考虑），jw 表示进位，lim 表示大小关系
int res[3][2][V+2]; // 用于卷积存储结果临时使用的数组
const int p = 998244353;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
dp[D][0][0] = dp[D][0][1] = 1;
dp2[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int m = 0; m <= V; ++m) {
dp2[i][m] = (dp2[i - 1][m] + (m >= a[i] ? dp2[i - 1][m - a[i]] : 0)) % p; // 处理 cnt 的值
}
}
for (int i = D - 1; i >= 0; --i) {
int dig = (m >> i) & 1; // m 的第 i 位
for (int jw = 0; jw <= 1; ++jw) for (int lim = 0; lim <= 2; ++lim) { // 对于每一种 jw 的奇偶性（并非 jw 本身）和 lim 标记做卷积
vector<int> a(V/2+1), b(V+1), c;
for (int j = 0; j <= V/2; ++j) a[V/2-j] = dp2[n][j*2+jw]; // 翻转序列
for (int j = 0; j <= V; ++j) b[j] = dp[i+1][j][lim];
c = atcoder::convolution(a, b);
for (int j = 0; j <= V/2; ++j) res[lim][jw][j] = c[V/2 + j] % p; // 从结果提取需要的部分
}
for (int jw = 0; jw <= V; ++jw) for (int lim = 0; lim <= 2; ++lim) {
dp[i][jw][lim] = (res[dig?0:lim][jw&1][(jw+1)/2] + res[dig?lim:2][!(jw&1)][jw/2]) % p;
// 这里的 dig?0:lim 之类的东西是数位 dp 的标记更新，省去了一些没必要的条件判断。
}
}
cout << dp[0][0][1] << "\n";
return 0;
}
```
[AC-Link](https://atcoder.jp/contests/abc436/submissions/71740309)
不得不说 AC 库的板子就是快，赛时贺的一个模板要跑 800 多毫秒。
## 总结
做法核心就是数位 DP 并且根据奇偶性化式子得到卷积形式。
这个数位 DP trick 也在 [Codeforces-1290F](https://codeforces.com/problemset/problem/1290/F) 一题中也有应用，只不过不需要卷积，而是需要一些奇妙的计算几何知识。感兴趣的读者可以去尝试。