自动搬运

查看原文

来自洛谷，原作者为

	LostKeyToReach 争取今年不退役 || int_stl. || 有意互关私。

搬运于2025-08-24 23:11:39，当前版本为作者最后更新于2025-03-23 10:32:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

笑点解析：赛时使用封装的取模类导致 $100$ 变 $65$。

海亮是不是人均多项式代师啊。

这是一个不用动脑子的做法。我们不妨设答案为 $f(n, x)$，则对于所有 $m \in \N$ 都有：

$$\begin{aligned} f(2^m - 1, x) &= \sum_{i = 0} ^ {2^m - 1} (-1)^{\text{popcnt}(i)}(i + x)^k \\ &= \sum_{S \subseteq \{0, 1, \ldots, m - 1\}}(-1)^{|S|}\left(i + \sum_{v \in S}2^v\right)^k. \end{aligned} $$

这样只对 $n = 2^m - 1$ 有用，那么怎么处理普通情况？我们令 $m$ 为 $n + 1$ 最高位对应的幂，那么原式变为：

$$\begin{aligned} f(n, x) &= f(2^m - 1, x) + \sum_{i = 2^m}^n (-1)^{\text{popcnt}(i)}(i + x)^k \\ &= f(2^m - 1, x) + \sum_{i = 0}^{n - 2^m}(-1)^{\text{popcnt}(i + 2^m)}[x + (i + 2^m)]^k \\ &= f(2^m - 1, x) - \sum_{i = 0}^{n - 2^m}(-1)^{\text{popcnt}(i)}[(x + 2^m) + i]^k \\ &= f(2^m - 1, x) - f(n - 2^m, x + 2^m). \end{aligned} $$

接下来我们对 $f(2^m - 1, x)$ 根据二项式定理进行展开：

$$\begin{aligned} f(2^m - 1, x) &= \sum_{S \subseteq \{0, 1, \ldots, m - 1\}}(-1)^{|S|}\left(i + \sum_{v \in S}2^v\right)^k \\ &= \sum_{S \subseteq \{0, 1, \ldots, m - 1\}}(-1)^{|S|}\sum_{i = 0} ^ k {k \choose i}x^{k - i}\left(\sum_{v \in S}2^v\right)^i \\ &= \sum_{i = 0} ^ k {k \choose i}x^{k - i}\sum_{S \subseteq \{0, 1, \ldots, m - 1\}}(-1)^{|S|}\left(\sum_{v \in S}2^v\right)^i. \\ \end{aligned} $$

考虑给 $\displaystyle x^{k - i}\sum_{S \subseteq \{0, 1, \ldots, m - 1\}}(-1)^{|S|}\left(\sum_{v \in S}2^v\right)^i$ 构造指数生成函数，那么这一部分所构成的答案为：

$$\begin{aligned} \prod_{i = 0} ^{m - 1}\left(1 - e^{2^it}\right) &= \prod_{i = 0} ^{m - 1}\left(-\sum_{j = 1} ^ {\infty}\frac{2^{ij}}{j!}t^{j}\right). \end{aligned} $$

组合意义显然，那么第 $i$ 项的系数便是答案。所以我们用 NTT 预处理一下多项式再上一个记忆化搜索就做完了，时间复杂度 $\mathcal{O}(k\log k\log n)$。

参考代码：

VVI polys, polyss;
int n, x, k;
VI fact, ifact;
void prepare() {
    polys.resize(46);
    fact.resize(k + 1, 0);
    ifact.resize(k + 1, 0);
    fact[0] = 1;
    For(i, 1, k) fact[i] = modMul(fact[i - 1], i);
    For(i, 0, k) ifact[i] = power(fact[i], mod - 2);
    For(i, 0, 45) {
        polys[i].resize(k + 1, 0);
        For(r, 0, k) {
            if (r == 0) {
                continue;
            }
            polys[i][r] = modMul(-power(2, i * r), ifact[r]);
        }
    }
    polyss.resize(46);
    polyss[0].resize(k + 1, 0);
    polyss[0][0] = 1;
    For(i, 0, 44) polyss[i + 1] = convolution(polyss[i], polys[i], k);
}
int calc(int m, int x, int kk) {
    int ans = 0;
    For(j, 0, kk) {
        ans = modAdd(ans, modMul(modMul(modMul(modMul(modMul(fact[k], ifact[j]), 
            ifact[k - j]), power(x, kk - j)), polyss[m][j]), fact[j]));
    }
    return ans;
}
std::map<PII, int> mp;
int solve(int n, int x) {
    if (n == -1) return 0;
    if (mp.find({n, x}) != mp.end())
        return mp[{n, x}];
    int m = 64 - __builtin_clzll(n + 1) - 1;
    int p = 1LL << m;
    if (n == p - 1) return mp[{n, x}] = calc(m, x, k);
    else {
        return mp[{n, x}] = modSub(calc(m, x, k), solve(n - p, (x + p) % mod));
    }
}
#define MULTI_TEST 0
int32_t main() {
#if MULTI_TEST == 1
#else
    std::cin >> n >> x >> k;
    prepare();
    std::cout << solve(n, x) << "\n";
#endif
}