[FJSC2014]化合物

浏览数：22 / 时间：2015年06月09日

【题目描述】

　　首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。

　　这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏，这个游戏很蛋疼，我相信你们也没有兴趣听。

　　由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。

　　他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成了一个树结构，1号分子为根。

　　若两个原子i、j到它们的最近公共祖先的距离分别是li和lj，定义它们的Aij值为：

Aij = li xor lj

　　题目要求对于每一个k（k∈N），求出两两A值为k的原子对个数。

【输入格式】

　　第一行一个整数N。

　　接下来N-1行，每行一个整数p，第i行的整数表示第i个原子的父亲为p。

【输出格式】

　　从k=0开始，第k+1行输出两两A值为k的原子对个数，输出到最后一个不为零的数为止。

【样例输入】

【样例输出】

【数据范围】用h表示树结构分子的最大深度。

　　40%：N<=1000,h<=30

　　70%：N<=3000,h<=100

　　100%：N<=100000,h<=500

Solution

　　暴力70分啊。。。。。。这么良心。

　　100%：类似树分治的做法，只不过每次只能选指定的非叶子结点。

　　考虑子树中经过根的路径对答案造成的影响，记f[x][j]表示以x结点为根的子树，与x结点距离为j的结点数。显然可以通过dfs转移。影响分两种：

　　1.以x为起点的链。ans[j]+=f[x][j];

　　2.端点在不同子树内。比如下面这组数据：

　　　　N=6，fa[]={0,1,1,2,2,2}

　　有f[2]={1,3},f[3]={1}.

　　两个数组乘起来，什么事都解决了。

　　其实这叫母函数= =

　　f[2]=x+3x^2,f[3]=x

　　本来f[2]*f[3]=x^2+3x^3

　　但是这是异或，所以指数上不能相加而是异或，于是f[2]*f[3]=1+3x^3

　　如果有多个子树，就两两暴力乘吧。异或这种东西不知道还是不要玩为妙。

　　然后这还只是暴力，标程把乘法的O(n^2)用fwt降成了O(nlogn)，真是寂寞如雪= =

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<ctime>
 5 #include<algorithm>
 6 int fa[100010];
 7 int main()
 8 {
 9     freopen("che.in","w",stdout);
10     srand(time(0));
11     int n=100000;printf("%d\n",n);
12     for(int i=2;i<=400;i++)printf("%d ",rand()%(i-1));
13     for(int i=401;i<=n;i++)printf("%d ",rand()%200+i-200);
14 }

Data Maker

 1 #include<cstdio>
 2 #include<cstring>
 3 int fa[100010],n,dep[100010],q[100010],l,r,max,tmp,a[600];long long ans[600];
 4 struct E{int to,nxt;}e[100010];
 5 int et,la[100010];
 6 void add(int x,int y){e[++et]=(E){y,la[x]};la[x]=et;}
 7 int lca(int x)
 8 {
 9     for(;x;x=fa[x])if(a[dep[x]]==x)break;
10     return x;
11 }
12 int main()
13 {
14     scanf("%d",&n);int i,j,k;dep[1]=1;
15     for(i=2;i<=n;i++)scanf("%d",&fa[i]),add(fa[i],i);
16     for(q[l=r=1]=1;l<=r;l++)
17     for(i=la[q[l]];i;i=e[i].nxt)
18     if(!dep[e[i].to])
19     dep[q[++r]=e[i].to]=dep[q[l]]+1;
20     for(i=1;i<n;i++)
21     {
22         memset(a,0,sizeof(a));
23         for(j=i;j;j=fa[j])a[dep[j]]=j;
24         for(j=i+1;j<=n;j++)
25         {
26             k=lca(j);
27 //            printf("i=%d j=%d k=%d ans=%d %d\n",i,j,k,(dep[i]-dep[k]),(dep[j]-dep[k]));
28             ans[tmp=(dep[i]-dep[k])^(dep[j]-dep[k])]++;
29             if(max<tmp)max=tmp;
30         }
31     }
32     for(k=0;k<=max;k++)printf("%lld\n",ans[k]);
33 }
34 /*
35 9
36 1 1 2 2 2 3 7 7
37 */

70%

 1 #include<cstdio>
 2 #include<cstring>
 3 const int MAXN=100010,MAXM=1025;
 4 long long ans[MAXM],tmp2[MAXM];
 5 int fa[MAXN],n,dep[MAXN],q[MAXN],l,r,max,tmp[MAXM],et,la[MAXN],f[MAXN][MAXM],mdep[MAXN];
 6 struct E{int to,nxt;}e[MAXN];
 7 void add(int x,int y){e[++et]=(E){y,la[x]},la[x]=et;}
 8 void mult(int*a,int*b,int&n)
 9 {
10     memset(tmp2,0,sizeof(tmp2));int i,j,c=0,t=n;
11     for(i=0;i<=n;i++)if(a[i])
12     for(j=0;j<=n;j++)if(b[j])
13     tmp2[c=((i+1)^(j+1))]+=1LL*a[i]*b[j],t<c?t=c:1;
14     for(n=t,i=0;i<=n;i++)ans[i]+=tmp2[i];
15 }
16 void dfs(int x)
17 {
18     bool flag=0;int i,j;
19     for(i=la[x];i;i=e[i].nxt)
20     {
21         dfs(e[i].to);
22         if(mdep[x]<mdep[e[i].to])mdep[x]=mdep[e[i].to];
23         for(j=0;j<=mdep[x];j++)f[x][j+1]+=f[e[i].to][j];
24     }
25     for(i=la[x];i;i=e[i].nxt)
26     for(j=e[i].nxt;j;j=e[j].nxt)
27     mult(f[e[i].to],f[e[j].to],mdep[x]);
28     f[x][0]++;mdep[x]++;
29     for(i=1;i<=mdep[x];i++)ans[i]+=f[x][i];
30 }
31 int main()
32 {
33     scanf("%d",&n);int i,j,k;dep[1]=1;
34     for(i=2;i<=n;i++)scanf("%d",&fa[i]),add(fa[i],i);
35     for(q[l=r=1]=1;l<=r;l++)
36     for(i=la[q[l]];i;i=e[i].nxt)
37     if(!dep[e[i].to])
38     dep[q[++r]=e[i].to]=dep[q[l]]+1;
39     for(dfs(1),max=1024;!ans[max];max--);
40     for(k=0;k<=max;k++)printf("%lld\n",ans[k]);
41 }