模拟赛
怎么都找不到原题了？
T1 博弈
trick，容易发现如果有一个数在路径上的出现次数为奇数，那么先手就能赢。
问题是如何判断路径上是否有一个数出现奇数次。
是一个存在性问题，考虑异或哈希，发现如果两个相同的数异或和为零，并且 \(d_{u,v} = d_{root,u} \oplus d_{root,v}\)。
如果一条路径上每个数出现次数都是偶数，那么异或和为零。所以只需要判断是否有两个点到根的路径的异或和想通就好了。
异或hash
发现依旧是判断存在性问题，我们可以预处理出来每个长度合法序列的 hash 值，然后就可以用异或的方法 \(O(1)\) 判断一个区间是否合法了。
很好想 \(O(n^2)\) 的暴力，考虑分治枚举区间。假如我们找到了一个位置 \(x\)，那么在处理完所有过这个点且长度为 \(a_x\) 的区间后，剩下的合法区间一定都不含 \(x\)。
显然，\(x\) 应该是这段区间最大值所在的位置。从这里分治，由于每次遍历最大会是 \(\frac{n}{2}\)，所以复杂度就是 \(O(nlog(n))\)。（有点像启发式合并？）
注意单次 hash 容易被卡（脸黑），建议 hash 两次。
code
#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
#define LL long long
#define mx(x,y) (a[x]>a[y]?x:y)
#define jd(x,y) (((sum1[y]^sum1[x-1])==aim1[y-x+1])&&(sum2[y]^sum2[x-1])==aim2[y-x+1])
const int N = 3e5+5;
int n,a[N],st[N][25];
LL ans;
ULL aim1[N],mp1[N],sum1[N],sum2[N],aim2[N],mp2[N];
inline ULL rd(ULL sd) {return (sd<<13)+(sd<<17)+(sd<<5)+(sd+998244353);}
inline int get(int l,int r)
{
int k=__lg(r-l+1);
return mx(st[l][k],st[r-(1<<k)+1][k]);
}
void sol(int l,int r)
{
if(l>r) return;
if(l==r) return ans+=(a[l]==1),void(0);
int mid=get(l,r);
for(int i=max(l,mid-a[mid]+1);i+a[mid]-1<=r;i++)
if(jd(i,i+a[mid]-1)) ans++;
sol(l,mid-1); sol(mid+1,r);
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
srand(time(0));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
mp1[i]=rd((ULL)rand()); mp2[i]=rd((ULL)rand());
aim1[i]=aim1[i-1]^mp1[i]; aim2[i]=aim2[i-1]^mp2[i];
}
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum1[i]=sum1[i-1]^mp1[a[i]],sum2[i]=sum2[i-1]^mp2[a[i]],st[i][0]=i;
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[j][i]=mx(st[j][i-1],st[j+(1<<i-1)][i-1]);
sol(1,n);
printf("%lld\n",ans);
return 0;
}
code
#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
const int N = 5e5+5;
int T,n;
unordered_map<int,ULL> mp;
ULL rd(ULL seed)
{
return (seed<<13)+(seed<<17)+(seed+998244353>>3);
}
int head[N],tot;
struct E {int u,v; ULL w;} e[N<<1];
inline void add(int u,int v,ULL w) {e[++tot]={head[u],v,w}; head[u]=tot;}
ULL d[N];
void dfs(int u,int f)
{
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v; if(v==f) continue;
d[v]=d[u]^e[i].w; dfs(v,u);
}
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
srand(time(0));
scanf("%d",&T);
while(T--)
{
memset(head,0,sizeof(head)); tot=0;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
if(!mp[z]) mp[z]=rd((ULL)rand());
add(x,y,mp[z]); add(y,x,mp[z]);
}
dfs(1,0);
sort(d+1,d+1+n);
long long ans=(1ll*n)*(n-1)/2;
for(int i=1,c=0;i<=n;i++)
{
c++;
if(d[i]!=d[i+1]) ans-=(1ll*c)*(c-1)/2,c=0;
}
printf("%lld\n",ans);
}
return 0;
}