题意简述

$n$ 个车厢排成一排，初始各自独立。每次可以把相邻的两组车厢合并，前提是两组大小之差不超过 $d$。合并大小为 $w$（左）和 $v$（右）的两组，代价为 $(aw + bv) \bmod 1001$。求把所有车厢合并成一组的最小总代价。

$n \le 10^{16}$，$d, a, b \le 1000$。

做法

拿到题先想合并过程的结构。每次合并相邻两组，其实就是在建一棵二叉树——叶子对应车厢，内部节点对应一次合并，"只能合并相邻的组"意味着中序遍历恰好是 $1, 2, \dots, n$。

换个角度：把 $n$ 个车厢合并成一组，等价于选一个分裂点 $k$，先把前 $k$ 个合并，再把后 $n - k$ 个合并，最后合并这两组。约束 $|w - v| \le d$ 就变成 $|2k - n| \le d$。

设 $f(n)$ 为合并 $n$ 个车厢的最小代价：

$$f(n) = \min_{k} \left\{ f(k) + f(n-k) + (ak + b(n-k)) \bmod 1001 \right\}$$

其中 $k$ 的范围是

$$\max\!\left(1,\, \left\lceil \frac{n-d}{2} \right\rceil\right) \le k \le \min\!\left(n-1,\, \left\lfloor \frac{n+d}{2} \right\rfloor\right)$$

边界 $f(1) = 0$。

到这里框架有了，但 $n$ 高达 $10^{16}$，直接递归肯定不行。得想想递归过程中到底会出现多少个不同的子问题。

注意到从 $n$ 开始，分裂成 $k$ 和 $n-k$，$k$ 在 $\lfloor n/2 \rfloor$ 附近，偏移量不超过 $\lfloor d/2 \rfloor$。所以第 $1$ 层产生的值在 $n/2$ 附近宽度约 $d$ 的区间里，第 $2$ 层在 $n/4$ 附近、宽度约 $\frac{3}{2}d$……第 $t$ 层集中在 $n/2^t$ 附近，宽度大约 $O(td)$。递归深度 $O(\log n)$，不同的 $n$ 值总数大约

$$\sum_{t=0}^{\log n} O(td) = O(d \log^2 n)$$

代入 $d = 1000$，$\log_2(10^{16}) \approx 54$，状态数大概 $1.5 \times 10^6$，没问题。每个状态枚举 $O(d)$ 个分裂点，总计算量 $O(d^2 \log^2 n)$，大概 $10^9$ 量级，但内部操作就是加法取模比较，常数很小，能过。

实现用 unordered_map 记忆化。几个细节：

• $(ak + b(n-k)) \bmod 1001$ 里 $k$ 可以很大，直接乘会溢出，先对 $1001$ 取模再乘。
• 答案可能接近 $10^{19}$，long long 会溢出，用 unsigned long long。
• 递归深度只有约 $54$ 层，栈没问题。
• unordered_map 对 long long 的默认哈希容易被卡，这里用了自定义哈希。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct MyHash {
    size_t operator()(ll x) const {
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9LL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebLL;
        return x ^ (x >> 31);
    }
};

ll D, A, B;
unordered_map<ll, ull, MyHash> memo;

ull solve(ll n) {
    if (n <= 1) return 0;
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;

    ll lo = max(1LL, (n - D + 1) / 2);
    ll hi = min(n - 1, (n + D) / 2);

    ull best = (ull)(-1);
    for (ll k = lo; k <= hi; k++) {
        int c = (int)((A * (k % 1001) + B * ((n - k) % 1001)) % 1001);
        ull val = solve(k) + solve(n - k) + c;
        if (val < best) best = val;
    }

    memo[n] = best;
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N >> D >> A >> B;
    cout << solve(N) << "\n";
    return 0;
}

:::info[AI 使用说明] 写作完成后，使用 Claude-opus 润色了部分段落表述并优化了代码可读性 :::