T1 四舍五入
假设有 \(\frac{a}{b}\),向下取整和四舍五入结果相同当且仅当 \(a\bmod b<\frac{b}{2}\),然后这个东西枚举除数很好做,但是这题让正着做,所以就相当于倒着区间加,复杂度是调和级数。
T2 填算符
神秘东西。
先按位考虑,发现最终的答案与和或都是连续的,可能中间会分一下,再简单分析一下,发现把与全放前面的答案一定可以是最优的,证明就是最后的数决定有无,所以直接保证最后的数全有即可。
然后考虑有那些或和与可以交换位置,贪心的从后检查每一个或,指针为 \(i\),然后再检查贪心的检查最后一个与,指针为 \(j\),由于这个东西有单调性,所以 \(i\) 指针是单调递减的,它之后的符号都是确定的,考虑在这个过程中,处理出后面的东西,然后对于检查是否可行,就是到当前 \(j\) 位置的与或上一段或后,看看是否能满足答案的最低要求,如果交换成功,答案的要求不变,否则后面多或了一个数,可以降低答案的要求。
讲的什么东西,自己看了都蚌埠住,你还是看别人的去吧。
T3 道路修建
不是很清新的数据结构,有经典 trick
:路径长度转化为边的经过次数。
考虑环边和树边,来一张图
环上的点都带一棵子树,所以环上每条边的经过次数是 \({n\choose 2}-\sum{size\choose 2}\)。
再考虑树边,首先有子树内的情况,然后还有向外的情况,向外的情况连向每一个点有两种方案,发现子树内的情况统计比较麻烦,但是这种情况在加边前就有了,而向外的情况有一半也在加边前有了,所以考虑只计算新的贡献。
环上的边的新贡献:在上一个基础上,每条边减去加边前的经过次数 \(sizet_u(n-sizet_u)\),所以总次数就是 \(m({n\choose 2}-\sum{size\choose 2})-\sum{sizet_u(n-sizet_u)}\)。
树边的新贡献:\(\sum sum_u(n-size_u)=n\sum sum_u-\sum sum_usize_u\)。
\(size_u,sum_u\) 分别表示子树大小,子树内节点到子树根的距离之和,由于这是一个环,所以除了 \(sizet_u\),其他信息都表示 \(u\) 的父亲除去儿子 \(u\) 的信息,端点信息特殊处理,\(LCA\) 处换根处理信息。倍增维护 \(size_u,sum_u,sum_usize_u,sizet_u(n-sizet_u)\) 即可。
两部分的和加上原来的贡献就是答案,原来的答案直接搜一遍得出。
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=3e5+10,mod=998244353,inf=1e9,ny=499122177;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
int n,Q,type,size[N],sum[N],ans,dfn[N],dn,lastans,de[N],rt[N];
int size_[20][N],sfa[20][N],sum_[20][N],mul[20][N],at[20][N],st[20][N];
std::vector<int> e[N];
inline void dfs(int x,int fa,int dep){
de[x]=dep;size[x]=1;sfa[0][x]=fa;st[0][dfn[x]=++dn]=fa;
for(int i=1;i<=std::__lg(dep);++i)sfa[i][x]=sfa[i-1][sfa[i-1][x]];
for(int v:e[x]){
if(v==fa)continue;
dfs(v,x,dep+1);W(size[x],size[v]);W(ans,size[v]*(n-size[v]));W(sum[x],sum[v]+size[v]);
}
for(int v:e[x]){
if(v==fa)continue;
sum_[0][v]=sum[x]-sum[v]-size[v];
size_[0][v]=(size[x]-size[v])*(size[x]-size[v])%mod;
at[0][v]=size[v]*(n-size[v])%mod;
mul[0][v]=sum_[0][v]*(size[x]-size[v])%mod;
}
}
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline void init(){for(int i=1;i<=std::__lg(n);++i)for(int j=1;j+(1<<i)-1<=n;++j)st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);}
inline int LCA(int u,int v){
if(u==v)return u;
if((u=dfn[u])>(v=dfn[v]))std::swap(u,v);
int d=std::__lg(v-u++);
return get(st[d][u],st[d][v-(1<<d)+1]);
}
struct SOME{int fa,size,sum,at,mul;};
inline void dfs1(int x,int fa,int dep){
W(rt[x],rt[fa]-size[x]+n-size[x]);if(x==1)rt[x]=sum[x];
for(int i=1;i<=std::__lg(dep);++i){
W(sum_[i][x],sum_[i-1][x]+sum_[i-1][sfa[i-1][x]]),
W(size_[i][x],size_[i-1][x]+size_[i-1][sfa[i-1][x]]),
W(at[i][x],at[i-1][x]+at[i-1][sfa[i-1][x]]),
W(mul[i][x],mul[i-1][x]+mul[i-1][sfa[i-1][x]]);
}
for(int v:e[x])if(v!=fa)dfs1(v,x,dep+1);
}
inline SOME GET(int u,int k){
if(k<0)return {0,0,0,0,0};
if(k<=0)return {u,0,0,0,0};
SOME res={0,0,0,0,0};
for(int i=std::__lg(k);~i;--i){
if((k>>i)&1){
W(res.size,size_[i][u]);W(res.sum,sum_[i][u]);W(res.mul,mul[i][u]);W(res.at,at[i][u]);
u=sfa[i][u];
}
}res.fa=u;
return res;
}
inline SOME ROOT(int u,int v,int lca){
int a=n-size[u]-size[v],b=rt[lca]-sum[u]-size[u]-sum[v]-size[v];
return{0,a*a%mod,b,(size[v]*(n-size[v])+size[u]*(n-size[u]))%mod,a*b%mod};
}
inline void ask(int u,int v){
int lca=LCA(u,v),L=1;
int k=de[u]-de[lca]-1;L+=k+1;auto it1=GET(u,k);if(u!=lca)W(it1.size,size[u]*size[u]),W(it1.sum,sum[u]),W(it1.mul,size[u]*sum[u]);
k=de[v]-de[lca]-1;L+=k+1;auto it2=GET(v,k);if(v!=lca)W(it2.size,size[v]*size[v]),W(it2.sum,sum[v]),W(it2.mul,size[v]*sum[v]);
auto it3=ROOT(it1.fa,it2.fa,lca);
int sizesum=it1.size+it2.size+it3.size,yuan=it1.at+it2.at+it3.at,ss=it1.sum+it2.sum+it3.sum,smul=it1.mul+it2.mul+it3.mul;
lastans=(L*(n*n-sizesum)%mod*ny%mod-yuan+n*ss%mod-smul)%mod;lastans=(lastans+ans+mod)%mod;
std::cout<<lastans<<'\n';lastans*=type;
}
signed main(){
freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),Q=read(),type=read();
for(int i=1;i<n;++i){int u=read(),v=read();e[u].eb(v);e[v].eb(u);}
dfs(1,0,0);dfs1(1,0,0);init();
while(Q--)ask(read()^lastans,read()^lastans);
}
T4 逆序图
计数,不会。
总结
打的退役分,T2 不会高分暴力,T3,T4 一点不会,菜逼。
标签:NOIP,int,sum,it1,mod,it2,模拟,size From: https://www.cnblogs.com/Ishar-zdl/p/18533149