P4065 [JXOI2017]颜色

题面

　　• get到一种 hash 乱搞。

　　• 考虑题目要求如何在 hash 值中得以体现。

　　• 为每个数赋上一个 hash 值，使得同一类数的 hash 值为零。

　　• 那么满足要求的序列的 hash 值之和一定为零。

 1 #include<bits/stdc++.h>
 2 #define ll unsigned long long
 3 using namespace std;
 4 int t,n,x,tot;
 5 int    head[300050];
 6 int nex[300050];
 7 int ver[300050];
 8 ll s[300050];
 9 ll ans,tmp;
10 void add(int x,int y)
11 {
12     nex[++tot]=head[x];
13     ver[tot]=y;
14     head[x]=tot;
15 }
16 ll randm()
17 {
18     ll cnt=rand()*rand();
19     if(rand()&1)    return cnt;
20     else    return -cnt;
21 }
22 int main()
23 {
24     srand(time(0));
25     scanf("%d",&t);
26     while(t--)
27     {
28         scanf("%d",&n);tot=0;
29         memset(head,0,sizeof(head));
30         for(int i=1;i<=n;++i)
31         {
32             scanf("%d",&x);
33             add(x,i);
34         }
35         for(int i=1;i<=n;++i)
36         {
37             tmp=0;
38             for(int j=nex[head[i]];j;j=nex[j])
39             {
40                 s[ver[j]]=randm();
41                 tmp-=s[ver[j]];
42             }
43             s[ver[head[i]]]=tmp;
44         }
45         s[0]=0;ans=0;
46         for(int i=1;i<=n;++i)
47             s[i]+=s[i-1];
48         sort(s,s+n+1);
49         for(int i=0,j=0;i<=n;++j,i=j)
50         {
51             while(s[j+1]==s[i]&&j<n)
52                 ++j;
53             ans+=(ll)(j-i)*(j-i+1)/2;
54         }
55         printf("%lld
",ans);
56     }
57     return 0;
58 }

hash 乱搞