题解：CF2028F Alice's Adventures in Addition

· · 题解

思路

显然 dp.

我们设 dp_{i, j} 表示前 i 个元素能否凑出 j。

可以考虑将乘起来的划分为一个段，那么对于每一个 i，可以枚举上一个段的下一个元素 k，我们设从 k\sim i 的乘积

\prod\limits_{w = k}^i a_w = c.

那么易得 dp 的转移方程为

dp_{i, j} = dp_{i, j}\vee dp_{k - 1, j - c}.

显然是会超时的，考虑优化。

我们注意到 m\leq 10^4，如果对于 \forall j\in [k, i]，均有 a_j>1，那么若 i - k + 1 \geq \log_2m，显然这一段的乘积已经大于 m，了，于是我们只需要枚举就近的 \log_2m 个 >1 的元素，可是万一存在 a_i = 0 或 1 呢？

若 a_i = 0：对于任意 1\leq k\leq i，此时 c = 0，所以

dp_{i, j} = dp_{i, j}\vee(\bigvee\limits_{k = 1}^i dp_{k - 1, j}).

此处可以用前缀或优化掉。

若 a_i = 1：如果 k\neq i 显然是无任何意义的，故必须单开一段，此时

dp_{i, j} = dp_{i, j}\vee dp_{i, j - 1}.

因为 0 和 1 的存在，枚举就近的 \log_2m 个 >1 的元素并不能保证时间复杂度，所以我们可以边转移的时候，边把 >1 的 a_i 扔进一个链表或者双端队列里面。

可是这样，会造成一个问题，如果 \exists w\in[k, i], a_w = 0.，那么我们计算的乘积就会变成正的，而非 0，怎么办呢？设这个 w 为 w_0，那么对于所有 1\leq k\leq w_0 的情况，均可以转化为

\begin{align*} dp_{i, j} &= dp_{i, j}\vee(\bigvee\limits_{k = 1}^{w_0} dp_{k - 1, j}) \\&=dp_{i, j}\vee dp_{w_0, j}. \end{align*}

因为如果我们将 0 都存下来，也不能保证时间复杂度，而又是位或运算，于是我们可以设一个中间量 z_{i, j} 作为 dp_{i,j} 所初始化的量。

如果我们每次都遍历一遍那些 a_w = 0 的位置，那么 z_{i,j} 当然是 0 啊，但是我们并不遍历，于是我们可以每次一遇到 0 便令

z_{i,j} = z_{i,j}\vee dp_{w_0, j}

即可，每次初始化 dp_{i,j} 就直接赋值。

综上所述

z_{i, j}\vee(\bigvee\limits_{k = 1}^i dp_{k - 1, j}) & (a_i = 0) \\ z_{i, j}\vee dp_{i, j - 1} & (a_i = 1) \\ z_{i, j}\vee dp_{k - 1, j - c} & (a_i>1) \end{cases}

在转移 dp_{i,j} 的同时，还要更新前缀或以及 z_{i,j}。

易发现这个过程可以用 biset 优化，此时时间复杂度为 O(\frac{nm\log m}{w})，空间限制没啥用，只需要存 \log_{2}m 个状态，根本不会超内存。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
#define inl inline
#define ls (p << 1)
#define rs (p << 1 | 1)
#define Cst constexpr
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define pb(x) push_back(x)
#define SZ(x) (int)(x).size()
#define ppc(x) __builtin_popcount(x)
#define All(x) (x).begin(), (x).end()
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))

Cst int lgM = 14, M = 1e4 + 5;
auto fIO = []() {
    return cin.tie(0)->sync_with_stdio(0), 0;
}();
int n, m;
bitset<M> dp, pre, z; 
deque<pair<int, bitset<M>>> q;
signed main() {
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        deque<pair<int, bitset<M>>>().swap(q);
        dp.reset(), pre.reset(), z.reset();
        dp[0] = pre[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int a; bitset<M> nxt = z; cin >> a;
            if (a == 0) { nxt |= pre; z = nxt, q.push_front({0, dp}); }
            else if(a == 1) nxt |= (dp | (dp << 1));
            else {
                long long mul = 1; q.push_front({a, dp});
                for (auto [f, s] : q) {
                    if (mul == 0 || mul * f > m) break;
                    mul *= f;
                    nxt |= s << mul;
                }
            } 
            pre |= nxt; dp = nxt;
            if (q.size() > lgM) q.pop_back();
        }
        cout << (dp[m] ? "YES" : "NO") << '\n';
    }
    return ~~(0 ^ 0);
}

::::