自动搬运

查看原文

来自洛谷，原作者为

	lnzwz **

搬运于2025-08-24 22:24:28，当前版本为作者最后更新于2020-10-06 20:34:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题我的方法比较奇怪。

题意：

有$k$种物品，第$i$个物品有$a_i$个，权值为$2^i$。

求有多少个$y$，使得可以选出$x$组物品，每组的和都为$y$。

先考虑如何判定一个$y$是否可行：

从最高位开始，依次求出第i位需要的数目$b_i$。若$y$的第$i$位为1，则$b\leftarrow b+x$。

如果$b_i \leq a_i$，那么说明$a_i$够用，进入下一位。

如果$b_i>a_i$，则选上所有$a_i$后，还剩$b_i-a_i$个。那么这些$2^i$只能用两倍的$2^{i-1}$来凑。因此把$b_{i-1}$加上$2 \times (b_i-a_i)$。

这样，只要$b_0<a_0$，则说明这个$y$可行。

可以发现，若$b_i \leq a_i$，那么对于所有$j<i$，$j$不会受之前的影响。

因此，可以把$b_i \leq a_i$作为分界点，进行DP。

设$dp_i$表示使得$b_i \leq a_i$的方案数目。只考虑大于等于$i$的位。那么，$dp_0$就是答案。

枚举$j>i$作为前一个分界点。那么，对于所有$i<c<j$，都要求$b_c>a_c$。

再枚举所有的$c$，那么$b_c$就可以很容易地用这个$y$在$[c,j-1]$这些数位上的值来表示。

于是，对于每个$c$，可以得出一条不等式。把这些不等式联立，就能得到$y$在$[i,j)$这些数位上的范围$d_{i,j}$。

因此，$dp_i\leftarrow dp_i+d_{i,j}\times dp_j$。

这样做的复杂度是$O(k^3q)$的，可以过。

代码：

#include <stdio.h>
#include <vector>
#include "biscuits.h"
using namespace std;
#define ll long long
ll dp[70];
ll count_tastiness(ll x, vector<ll> sz) {
    int k = sz.size();
    for (int i = 0; i < 62 - k; i++) sz.push_back(0);
    k = 62;
    for (int i = k; i >= 0; i--) {
        if (i == k) {
            dp[i] = 1;
            continue;
        }
        dp[i] = 0;
        for (int j = i + 1; j <= k; j++) {
            ll zx = 0, zd = (1ll << (j - i)) - 1, h = 0;
            for (int a = j - 1; a >= i; a--) {
                h = h * 2 + sz[a];
                ll z = (h / x + 1) << (a - i);
                if (a > i) {
                    if (z > zx)
                        zx = z;
                } else {
                    if (z - 1 < zd)
                        zd = z - 1;
                }
            }
            if (zx <= zd)
                dp[i] += dp[j] * (zd - zx + 1);
        }
    }
    return dp[0];
}

不难发现，求$d_{i,j}$的过程可以优化。提前预处理出$d_{i,j}$，就可以$O(k^2)$了。

#include <stdio.h>
#include <vector>
#include "biscuits.h"
using namespace std;
#define ll long long
ll dp[70], zz[70][70], dd[70][70];
ll count_tastiness(ll x, vector<ll> sz) {
    int k = sz.size();
    for (int i = 0; i < 62 - k; i++) sz.push_back(0);
    for (int j = 1; j <= 62; j++) {
        ll zx = 0, h = 0;
        for (int a = j - 1; a >= 0; a--) {
            zz[a][j] = zx;
            h = h * 2 + sz[a];
            ll z = (h / x + 1) << a;
            if (z > zx)
                zx = z;
            dd[a][j] = z;
        }
    }
    for (int i = 62; i >= 0; i--) {
        if (i == 62) {
            dp[i] = 1;
            continue;
        }
        dp[i] = 0;
        for (int j = i + 1; j <= 62; j++) {
            ll zx = (zz[i][j] >> i), zd = (1ll << (j - i));
            if ((dd[i][j] >> i) < zd)
                zd = (dd[i][j] >> i);
            if (zx <= zd)
                dp[i] += dp[j] * (zd - zx);
        }
    }
    return dp[0];
}