hdu6121

题意

给出一棵树，\(0\) 为根节点，节点 \(i\) 的父节点标号是 \(\lfloor\frac{i-1}{k}\rfloor\)，求所有子树大小的异或和。

分析

找规律。在纸上画个十几个一定可以找到规律（亲测有效）。

虽然数据很大，但是我们可以特判掉 \(k=1\) 的情况，同样有规律。

那么当 \(k > 1\) 时，树的叶子节点的数量的增长速度是很快的，而且叶子节点一定是连续分布的，也是说会有大量状态类似的子树，既然是求异或和，我们只需要判断有相同大小的子树的数量是否为奇数即可。

自底向上不断合并子树，记录几种状态的子树及其大小。

我这里分为三种：

可以独自向上合并而不需要借助其它节点的那些子树，也就是可以直接占据一个父节点
不能独自向上合并，必须借助第三类，或者由第一类多的子树转变而来
剩下的节点

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        ll n, k;

        scanf("%lld%lld", &n, &k);

        ll ans = 0;

        if(k == 1) {

            ll nn = n % 4;

            if(nn == 0) ans = n;

            else if(nn == 1) ans = 1;

            else if(nn == 2) ans = n + 1;

            else ans = 0;

        } else {

            ll sz = 1, lsz = 1;

            int cnt = 1;

            n--;

            while(n > 0) {

                sz = sz * k;

                if(n - sz < 0) break;

                n -= sz;

                lsz = sz;

                cnt++;

            }

            ll cnt1 = 0, cnt2 = 0, cnt3 = 0;

            ll sz1 = 0, sz2 = 0, sz3 = 0;

            if(n > 0) {

                ans ^= (n & 1);

                cnt1 = n / k; if(cnt1 > 0) sz1 = k + 1;

                if(n % k > 0) { cnt2 = 1; sz2 = n % k + 1; }

            }

            cnt3 = lsz - cnt1 - cnt2;

            sz3 = 1;

            while(cnt--) {

                ans ^= (cnt3 & 1) * sz3;

                ans ^= (cnt1 & 1) * sz1;

                ans ^= (cnt2 & 1) * sz2;

                if(cnt1 / k == 0) {

                    sz2 += sz1 * cnt1 + 1;

                    if(cnt1 + cnt2 < k) {

                        cnt3 -= k - cnt1 - cnt2;

                        sz2 += (k - cnt1 - cnt2) * sz3;

                        cnt2 = 1;

                    }

                    cnt1 = 0;

                    sz1 = 0;

                } else {

                    sz2 += sz1 * (cnt1 % k);

                    ll c = cnt1 % k + cnt2;

                    if(c < k) {

                        cnt3 -= k - c;

                        sz2 += (k - c) * sz3;

                    }

                    cnt2 = 1;

                    sz2++;

                    cnt1 = cnt1 / k;

                    sz1 = sz1 * k + 1;

                }

                cnt3 /= k;

                sz3 = sz3 * k + 1;

                if(cnt3 == 0) sz3 = 0;

            }

        }

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

hdu6121

hdu6121

题意

分析

code

最新文章

热门文章