题解：P11957 「ZHQOI R1」幂和

· · 题解

笑点解析：赛时使用封装的取模类导致 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
}