HDU 5593 ZYB's Tree 树形dp

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn=5e5+10;
 8 typedef long long LL;
 9 
10 int dp[maxn][11];
11 int fa[maxn];
12 int N,K,A,B;
13 
14 struct Edge{
15     int v,ne;
16     Edge(int v,int ne):v(v),ne(ne){}
17     Edge(){}
18 }egs[maxn*2];
19 
20 int head[maxn],tot;
21 
22 void addEdge(int u,int v){
23     egs[tot]=Edge(v,head[u]);
24     head[u]=tot++;
25 }
26 //从下往上跑一遍 
27 void dfs1(int u){
28     int p=head[u];
29     while(p!=-1){
30         Edge& e=egs[p];
31         dfs1(e.v);
32         for(int i=1;i<=K;i++){
33             //转移方程1： 
34             dp[u][i]+=dp[e.v][i-1];
35         }
36         p=e.ne;
37     }
38     dp[u][0]=1;
39 }
40 //从上往下跑一遍 
41 void dfs2(int u){
42     if(fa[u]){
43         for(int i=K;i>=2;i--){
44             //转移方程2： 
45             dp[u][i]+=dp[fa[u]][i-1]-dp[u][i-2];//dp[fa[u]][i-1]有包括u本身，所以要扣掉u的那部分对fa[u]的贡献 
46         }
47         dp[u][1]++;
48     }
49     int p=head[u];
50     while(p!=-1){
51         Edge& e=egs[p];
52         dfs2(e.v);
53         p=e.ne;
54     }
55 }
56 
57 void init(){
58     fa[1]=0;
59     memset(dp,0,sizeof(dp));
60     memset(head,-1,sizeof(head));
61     tot=0;
62 }
63 
64 int main(){
65     int tc;
66     scanf("%d",&tc);
67     while(tc--){
68         scanf("%d%d%d%d",&N,&K,&A,&B);
69         init();
70         for(int i=2;i<=N;i++){
71             int x=((LL)A*i+B)%(i-1)+1;
72             addEdge(x,i);
73             fa[i]=x;
74         }
75         dfs1(1);
76         dfs2(1);
77         LL ans=0;
78         for(int i=1;i<=N;i++){
79             int cnt=0;
80             for(int j=0;j<=K;j++) cnt+=dp[i][j];
81             ans^=cnt;
82         }
83         printf("%lld
",ans);
84     }
85     return 0;
86 }