可以发现这道题的数据范围有些奇怪，为毛n辣么大，而k只有10
我们从树形dp的角度来考虑这个问题。
如果我们设f[x][k]表示与x距离为k的点的数量，那么我们可以O(1)回答一个询问
可是这样的话dp貌似就比较麻烦了。
我们考虑一般树形dp都是怎样的，一般的树形dp，都是因为子树上的f值可以无后效的转移到根节点上，并且子树的f值与父亲无关，如果我们按照上述定义，那么就会发现这需要两遍dfs来解决，并且细节不少。
但是两遍dfs我并不会QAQ
所以我们考虑转换一种定义，设f[x][k]表示在以x为根的子树中距离不超过k的点数这样就可以很简单地直接dp了，但是统计答案的时候，我们发现一个点的上方的点我们都没有统计。
怎么解决这个问题呢？直接暴力跳转fa，利用fa的f值来补充答案，因为最多向上跳转10次，所以这个做法可行。
复杂度O(nk)
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = ;
const int maxk = ;
int f[maxn][maxk],fa[maxn],n,k;
inline void init(){
memset(f,,sizeof f);
memset(fa,,sizeof fa);
}
inline void work(){
init();
int A,B;read(n);read(k);read(A);read(B);
int ai;fa[] = ;
for(int i=;i<=n;++i){
ai = ((ll)A*i + (ll)B )%(i - ) + ;
fa[i] = ai;
//printf("%d %d\n",i,fa[i]);
}
for(int i=;i<=n;++i) f[i][] = ;
for(int j=;j<k;++j){
for(int i=;i<=n;++i){
f[fa[i]][j+] += f[i][j];
}
}
for(int j=;j<=k;++j){
for(int i=;i<=n;++i){
f[i][j] += f[i][j-];
}
}
int ans = ,res = ;
for(int i=;i<=n;++i){
res = f[i][k];
int j = ,x = fa[i];
for(int y=i;x != && j < k;y=x,x=fa[x],++j)
res += f[x][k-j] - f[y][k-j-];
if(j == k && x != ) ++ res;
//printf("%d--%d\n",i,res);
ans ^= res;
}
printf("%d\n",ans);
}
int main(){
freopen("skytree.in","r",stdin);
freopen("skytree.out","w",stdout);
int T;read(T);
while(T--) work();
getchar();getchar();
return ;
}