CERC 2017 Cumulative Code

pufanyi

发布于：Jan 31, 2020

给你一棵 $k\ (k\le 30)$ 阶的满二叉树，从上到下、从左到右从 $1$ 开始编号，设 $\{p_{n}\}$ 是它的 Prüfer 序列。给你三个数 $a,d,m$ ，求 $\sum_{i=0}^{m-1}p_{a+id}$ 。

这题主要是要发现一个性质，就是考虑定义 $f_{i,k,h}(x)$ 表示以 $x$ 为根，深度为 $k$ 的子树，现在要开始删的是 Prüfer 序列中的第 $i$ 位，对答案的共献， $h$ 表示 $x$ 是否有父亲，那么 $f_{i,k,h}(x)$ 可以表示成 $a_{i,k,h}x+b_{i,k,h}\lfloor\frac{x}{2}\rfloor+c_{i,k,h}$ 的形式。

令 $Q$ 表示询问集合，考虑左儿子对答案的贡献为 $f_{i,k-1,1}(2x)$ ，也就是对父亲的贡献是 $2a_{i,k-1,1}x+b_{i,k-1,1}\lfloor\frac{2x}{2}\rfloor+c_{i,k-1,1}=\left(2a_{i,k-1,1}+b_{i,k-1,1}\right)x+c_{i,k-1,1}$ ，即 $\{2a_{i,k-1,1}+b_{i,k-1,1},0,c_{i,k-1,1}\}$ ，右儿子同理可推出，为 $\{2a+b,0,a+c\}$ 。

我们考虑记搜，记搜的答案直接存的是 $a,b,c$ ，这样我们就可以省掉 $x$ 对答案的影响。我们发现 $i$ 其实可以表示成到下一个询问的距离，也就是其 lower_bound，这样我们可以省一点空间。

但是我们发现还是需要 $2^n$ 级别，我们考虑小范围暴搜，其余记搜，即 $k>15$ 是不计入状态，然后如果递归到一棵子树发现它没有询问节点，那么直接 return 掉，这样就使得 $i$ 小于等于子树 size 了。

其实 $h=0$ 我们也不用计入状态，因为不难发现 $h=0$ 只会搜索 $\mathcal{O}(k)$ 次，完全可以接受。

最后稍稍判一下边界即可。

这样深度小于等于 $\frac{k}{2}$ 的节点只有 $\mathcal{O}(2^\frac{k}{2})$ 个，深度大于 $\frac{k}{2}$ 的只有 $\mathcal{O}(k2^\frac{k}{2})$ 个，所以单次询问时空复杂度均为 $\mathcal{O}(k2^\frac{k}{2})$ 。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxl = 16;
const int lim = 15;

struct Solution {
    LL a, b, c;
    Solution (LL a = 0, LL b = 0, LL c = 0) { this->a = a, this->b = b, this->c = c; }
    inline LL calc(int x) { return a * x + b * (x >> 1) + c; }
} F[maxl][1 << maxl];

int vis[maxl][1 << maxl];

inline void addls(Solution& a, const Solution b) {
    a.a += 2 * b.a + b.b;
    a.c += b.c;
}

inline void addrs(Solution& a, const Solution b) {
    a.a += 2 * b.a + b.b;
    a.c += b.a + b.c;
}

int kase;

#define jian(x, y) { \
    x -= y; \
}

inline Solution f(int k, int first, int m, int d, bool h) {
    if (k == 1) {
        return Solution(0, 1, 0);
    }
    int siz = (1 << k) - 1;
    if (siz < first || !m) {
        return Solution(0, 0, 0);
    }
    bool flg = k <= lim && h && first + m * d >= siz;
    if (flg) {
        if (vis[k][first] == kase) {
            return F[k][first];
        }
    }
    int fstbak = first;
    Solution ans;
    int sizs = (1 << (k - 1)) - 1;
    Solution xx;
    if (first < sizs && m > 0) {
        int nowm = min(m, (sizs - first - 1) / d + 1);
        addls(ans, xx = f(k - 1, first, nowm, d, true));
        first += nowm * d;
        m -= nowm;
    }
    jian(first, sizs);
    if (!h) {
        if (m > 0 && !first) {
            ans.a += 2, ans.c++;
            first += d, m--;
        }
        jian(first, 1);
    }
    if (first < sizs && m > 0) {
        int nowm = min(m, (sizs - first - 1) / d + 1);
        addrs(ans, xx = f(k - 1, first, nowm, d, h));
        first += nowm * d;
        m -= nowm;
    }
    jian(first, sizs);
    if (h && m > 0) {
        ans.b++;
    }
    if (flg) {
        vis[k][fstbak] = kase;
        F[k][fstbak] = ans;
    }
    return ans;
}

int main() {
    int k, q;
    cin >> k >> q;
    while (q--) {
        int a, d, m;
        cin >> a >> d >> m;
        a--, kase++;
        Solution ans = f(k, a, m, d, false);
        cout << ans.a + ans.c << '\n';
    }
    return 0;
}