有一棵$n$个点的有根树，标号为$0$到$n-1$，iii号点的父亲是floor⌊​k​​i−1​​⌋号点，求所有子树大小的异或和。1≤n,k≤10​18​​。

这是一棵完全k叉树，考虑根的所有孩子，最多只有一个不是满k叉树，对这个孩子进行递归处理即可。k>1时只有log层，直接做就到底就好了，k=1时要特判。

1005

给定正整数$a$，求对于所有正整数bb，amodb有多少种可能的结果。1≤a≤10​9​​。

显然小于<a/2的每个非负整数c都是可能成为余数的，取b=a-c即可，另外a本身也能成为余数，而其他数显然都不可能。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            int n;
            cin>>n;
            cout<<((n+1)/2)+1<<endl;
        }    
        
    }
    return 0;
}

1008（极角排序是什么..待补）

平面直角坐标系上有nn个整点，第ii个点有一个点权val​i​​，坐标为(x​i​​,y​i​​)，其中不存在任意两点连成的直线经过原点。这些整点两两之间连有一条线段，线段的权值为其两端点的权值之积。你需要作一条过原点而不过任意一个给定整点的直线，使得和这条直线相交的线段的权值和最大。1≤n≤5×10​4​​,1≤val​i​​≤10​4​​,∣x​i​​∣,∣y​i​​∣≤10​9​​。

对于一条直线，线段权值和实际上就等于其两边点权和的乘积，所以把所有点按极角排个序，然后扫一圈就好了。

1010（待补..）

有一个长度为nn的整数序列{a​n​​}，对其做mm次前缀异或和，求最终的序列。1≤n≤2×10​5​​,1≤m≤10​9​​,0≤a​i​​≤2​30​​−1。

可以发现做m次后，位置为x的初始值对位置为y的最终值的贡献次数是一个只和m与y-x相关的组合式，而我们只关注这个次数的奇偶性。考虑Lucas定理，C(a,b)是奇数当且仅当把a,b二进制表达后b中1的位置是a中1的位置的子集，于是这里所有满足条件的b有很好的性质，对每一个二进制位独立处理就能算出答案。

1011

Kolakoski

Kolakoski序列是一个仅由1和2组成的无限数列，是一种通过“自描述”来定义的数列。他的前几项为
1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…
它的定义很简单，若把数列中相同的数定为一组，令a(1)=1，a(2)=2，则a(n)等于第n组数的长度。
可以根据这个定义来推算第三项以后的数：例如由于a(2)=2，因此第2组数的长度是2，因此a(3)=2,；
由于a(3)=2，所以第三组数的长度是2，因此a(4)=a(5)=1；由于a(4)=1，a(5)=1，所以第四组数和第五组数的长度都为1，因此a(6)=2，a(7)=1，以此类推

直接打表找规律 两个数列根据关系可以不断互推增长 int打个1e7的表还是可以存下的

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 1e7 +5;

int a[maxn] = {1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1};
int n;

int main()
{
    int indexa = 20;
    int indexb = 13;
    
    while(indexa < 1e7)
    {
        int temp = a[indexa - 1];
        if(temp == 1)
        {
            a[indexa] = 2;
        }
        else if(temp == 2)
        {
            a[indexa] = 1;
        }
        
        if(a[indexb] == 1)
        {
            indexa ++ ;
            indexb ++;
        }
        
        else if(a[indexb] == 2)
        {
            if(temp == 1)
            {
                a[indexa + 1] = 2;    
            }        
            
            else 
                a[indexa + 1] = 1;
                
            indexa +=2;
            indexb +=1;
        }
    }
    
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        cout<<a[n-1]<<endl;
    }
    
    return 0;
}