2023NOIP A层联测26 T4 abstract
乱证明求性质的光速幂优化题。
思路
对于每一个节点，到该节点的子树内的叶子节点的路径中（包括路径上的点），出现的值只有 \(k\times(\log V+\log V)\) 个。
那么在以该点为终点，以子树内节点为起点的路径中，取值只有 \(k\times(\log V+\log V)\)。
这是因为，如果以某个非叶节点为起点到该点的路径中，取值严格包含在：到该节点的子树内的叶子节点的路径中出现的值。
我们可以叶子开始向父亲传值，如果父亲有多个枝丫，那么将枝丫的结果合并，由于这样的枝丫不超过 \(k\) 个，此处为 \(O(k^2\log^2 V)\)。
那么最终时间复杂度为 \(O(k^2\log^2 V \log A+nk\log V \log A)\)。
此处 \(\log A\) 为快速幂时间复杂度。
为了消去这个 \(\log A\)，可以使用光速幂，\(O(1)\) 查询。
不过快速幂可以卡过（乐：D
CODE
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
const ll mod=111121,MOD=998244353;
const int maxn=1e5+5;
struct Edge
{
int to,nxt;
}edge[maxn*2];
struct Hash
{
int operator()(const pair<int,int> &x)const{
return (1ll*x.F*MOD+x.second)%MOD;
}
};
unordered_map< pair<int,int> , int, Hash >mp[maxn];//mp 记录某一点的二元组数量
int n,tot;
int a[maxn],head[maxn];
ll ans;
void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
ll ksm(ll x,ll y)
{
ll sum=1;
for(;y;y/=2,x=x*x%mod) if(y&1) sum=sum*x%mod;
return sum;
}
void dfs(int u,int f)
{
if(a[u])
{
mp[u][make_pair(a[u],a[u])]=1;
ans=(ans+ksm(a[u],a[u]))%mod;
}
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==f) continue;
dfs(v,u);
for(auto j:mp[u])
{
for(auto k:mp[v])
ans=(ans+ksm(j.F.F&k.F.F,j.F.S|k.F.S)*j.S%mod*k.S)%mod;
}
for(auto j:mp[v])
{
if(j.F.F&&a[u]) mp[u][make_pair(j.F.F&a[u],j.F.S|a[u])]+=j.S;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
printf("%lld",ans);
}