记录编号	343881	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]树之美	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.173 s
提交时间	2016-11-09 19:18:43	内存使用	100.43 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int N=1000010;
typedef long long ll;
int T,n,k,A,B,fa[N],cnt[N][20],Ans;
//cnt[i][j]表示以i为根，深度为j的节点个数 
int w[N],head[N],tail[N],next[N];
void add(int f,int x){
	if (!head[f]) head[f]=tail[f]=x;
		else tail[f]=next[tail[f]]=x;
}
int S[N],size;
void make_root(int x){
	for (int i=x;fa[i];i=fa[i]) S[++size]=i;;
	while (size){
		int v=S[size--],u=fa[v];
		if (!u) continue;
		for (int j=0;j<k;j++)
			cnt[u][j+1]-=cnt[v][j];
		for (int j=0;j<k;j++)
			cnt[v][j+1]+=cnt[u][j];
	}
	int last=0;
	for (int i=x;i;){
		int z=fa[i];
		fa[i]=last;
		last=i;i=z;
	}
}
bool vis[N];
void dfs(int x){
	vis[x]=1;make_root(x);
	int ans=0;
	for (int i=0;i<=k;i++) ans+=cnt[x][i];
	Ans^=ans;
	for (int i=head[x];i;i=next[i])
	if (!vis[w[i]]) dfs(w[i]);
}
int main()
{
	freopen("skytree.in","r",stdin);
	freopen("skytree.out","w",stdout);
	scanf("%d",&T);
	while (T--){
		memset(w,0,sizeof w);
		memset(next,0,sizeof next);
		memset(head,0,sizeof head);
		memset(cnt,0,sizeof cnt);
		memset(vis,0,sizeof vis);
		memset(fa,0,sizeof fa);
		scanf("%d%d%d%d",&n,&k,&A,&B);
		Ans=0;
		for (int i=2;i<=n;i++){
			fa[i]=((ll)A*i+B)%(i-1)+1;
			w[i]=fa[i];w[i+n]=i;
			add(i,i);add(fa[i],i+n);
		}
		cnt[1][0]=1;
		for (int i=n;i>1;i--){
			cnt[i][0]++;
			for (int j=0;j<k;j++)
				cnt[fa[i]][j+1]+=cnt[i][j];
		}
		dfs(1);
		printf("%d\n",Ans);
	}
	return 0;
}