DAY1

A. 剪切字符串

可以想到一个简单的贪心，
就是在最坏情况下，我两个字串长度都取 $1$，
此时 $\text{LCP}$ 最大为 $3$，即每个 $\text{LCP}$ 最大为 $1$。
所以我们贪心地认为 $i=1$，
此时可以对字符串 $c$ 中的每一个字母个数进行前缀和，
然后枚举 $j$，判断 $c$ 的字串中能否找到一个字母异于 $a_i$ 和 $b_j$。
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n;
string a,b,c;
int sum[N][30];
int main(){
	freopen("lcp.in","r",stdin);
	freopen("lcp.out","w",stdout);
	cin>>T;
	while(T--){
		memset(sum,0,sizeof sum);
		int ans=3;
		cin>>n>>a>>b>>c;
		a=" "+a,b=" "+b,c=" "+c;
		for(int i=1;i<=n;i++){
			for(int j=0;j<30;j++) sum[i][j]+=sum[i-1][j];
			sum[i][c[i]-'a']++;
		}
		for(int i=2;i<n;i++){
			if(a[1]==b[i]){
				int cnt=sum[n][a[1]-'a']-sum[i][a[1]-'a'];
				if(cnt<n-i) ans=min(ans,1);
				else ans=min(ans,3);
			}
			else{
				int cnt=(sum[n][a[1]-'a']-sum[i][a[1]-'a'])+(sum[n][b[i]-'a']-sum[i][b[i]-'a']);
				if(cnt<n-i) ans=min(ans,0);
				else ans=min(ans,1);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n;
string a,b,c;
int sum[N][30];
int main(){
	freopen("lcp.in","r",stdin);
	freopen("lcp.out","w",stdout);
	cin>>T;
	while(T--){
		memset(sum,0,sizeof sum);
		int ans=3;
		cin>>n>>a>>b>>c;
		a=" "+a,b=" "+b,c=" "+c;
		for(int i=1;i<=n;i++){
			for(int j=0;j<30;j++) sum[i][j]+=sum[i-1][j];
			sum[i][c[i]-'a']++;
		}
		for(int i=2;i<n;i++){
			if(a[1]==b[i]){
				int cnt=sum[n][a[1]-'a']-sum[i][a[1]-'a'];
				if(cnt<n-i) ans=min(ans,1);
				else ans=min(ans,3);
			}
			else{
				int cnt=(sum[n][a[1]-'a']-sum[i][a[1]-'a'])+(sum[n][b[i]-'a']-sum[i][b[i]-'a']);
				if(cnt<n-i) ans=min(ans,0);
				else ans=min(ans,1);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

DAY2

一看到是数学题，直接枚举了一下 $100$ 以内的符合题意的数对，
发现数对的一个充分不必要条件，即 $|a-b|= \gcd(a,b)$。
发现可以枚举 $\gcd$，
对于每一个 $i=\gcd$，循环判断每一个 $j \oplus (j+i)$ 是否与 $i$ 相等，
需要 $O(\sum^{n}_{i=1} \frac{n}{i})$ 的复杂度。
注意到：
$$
\sum^{n}_{i=1} \frac{n}{i} = n\sum^{n}_{i=1} \frac{1}{i}
$$
其中调和级数 $\sum^{n}_{i=1} \frac{1}{i}$ 满足：
$$
\sum^{n}_{i=1} \frac{1}{i} = \ln(n+1)+γ < \ln(n)
$$
其中 $γ≈0.5772156$，表示欧拉常数。
所以时间复杂度约为 $O(n\ln(n))$，在 $n=10^7$ 时不会超时。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
	freopen("gcdxor.in","r",stdin);
	freopen("gcdxor.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n>>1;i++) for(int j=i;j+i<=n;j+=i) if((j^(j+i))==i) ans++;
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
	freopen("gcdxor.in","r",stdin);
	freopen("gcdxor.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n>>1;i++) for(int j=i;j+i<=n;j+=i) if((j^(j+i))==i) ans++;
	cout<<ans;
	return 0;
}

B. 异或树

先讨论操作一：
对于每个点权为 $w$ 的叶子节点，
会新增两个点权分别为 $w$ 和 $w \oplus x$ 的子节点，
对于子树异或和的贡献为两个值为 $w \oplus x$ 的子树，
而对于叶子节点的贡献是新增一个点权为 $w \oplus x$ 的点。
所以很容易想到去枚举每一次操作后的叶子节点。
但是操作次数 $q≤8000$，又发现 $k_0, x \in [0,2^{13})$，
想到可以用两个桶数组分别存储答案和每个值对应叶子节点数量，
并再用一个桶数组表示每个值新增叶子节点的数量，
最后转移到总叶子节点桶数组即可，可以避免在同层加叶子节点时重复计算。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int N=8200,mod=998244353;
int k,q;
int t[N],tag[N],ntag[N];
signed main(){
	freopen("xortree.in","r",stdin);
	freopen("xortree.out","w",stdout);
	k=read(),q=read();
	t[k]=tag[k]=1;
	while(q--){
		int op,x;
		op=read(),x=read();
		if(op==1){
			for(int i=0;i<N;i++) if(tag[i]){
				(ntag[(i^x)]+=tag[i])%=mod;
				(t[(i^x)]+=2*tag[i])%=mod;
			}
			for(int i=0;i<N;i++) (tag[i]+=ntag[i])%=mod,ntag[i]=0;
		}
		else if(op==2) printf("%lld\n",t[x]%mod);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int N=8200,mod=998244353;
int k,q;
int t[N],tag[N],ntag[N];
signed main(){
	freopen("xortree.in","r",stdin);
	freopen("xortree.out","w",stdout);
	k=read(),q=read();
	t[k]=tag[k]=1;
	while(q--){
		int op,x;
		op=read(),x=read();
		if(op==1){
			for(int i=0;i<N;i++) if(tag[i]){
				(ntag[(i^x)]+=tag[i])%=mod;
				(t[(i^x)]+=2*tag[i])%=mod;
			}
			for(int i=0;i<N;i++) (tag[i]+=ntag[i])%=mod,ntag[i]=0;
		}
		else if(op==2) printf("%lld\n",t[x]%mod);
	}
	return 0;
}