ie兼容性 网站,上海市虹口市容建设公司网站,广州网站建设 app 小程序,濮阳网站制作正题
题目链接:http://www.ybtoj.com.cn/contest/125/problem/2 题目大意
给出nnn个点的一棵树#xff0c;以111为根#xff0c;每个点有点权aia_iai。要求支持mmm次操作
修改一个修改一个节点的父节点修改一条路径的权值为www给出uuu询问Fbi(au)Fbi(a_u)Fbi(au)给出u…正题
题目链接:http://www.ybtoj.com.cn/contest/125/problem/2 题目大意
给出nnn个点的一棵树以111为根每个点有点权aia_iai。要求支持mmm次操作
修改一个修改一个节点的父节点修改一条路径的权值为www给出uuu询问Fbi(au)Fbi(a_u)Fbi(au)给出u,vu,vu,v将路径u−vu-vu−v的点权排列好后设为bbb求 ∑i1k∑jikFbi(∑zijbz)\sum_{i1}^k\sum_{ji}^kFbi(\sum_{zi}^jb_z)i1∑kji∑kFbi(zi∑jbz)
其中Fbi(i)Fbi(i)Fbi(i)表示第iii个斐波那契数。输出答案模998244353998244353998244353的值
1≤n,m≤105,ai,w∈[1,109]1\leq n,m\leq 10^5,a_i,w\in[1,10^9]1≤n,m≤105,ai,w∈[1,109] 解题思路
嗯这个斐波那契很麻烦可以考虑一些用特征方程1−x−x201-x-x^201−x−x20可以得到斐波那契的通项公式 Fbi(n)(512)n−(5−12)n5Fbi(n)\frac{(\frac{\sqrt 51}{2})^n-(\frac{\sqrt 5-1}{2})^n}{\sqrt 5}Fbi(n)5(251)n−(25−1)n 为了方便上面5±12\frac{\sqrt 5\pm 1}{2}25±1分别记为X0,X1X_0,X_1X0,X1。 那么如果设ciX0ai,diX1aic_iX_0^{a_i},d_iX_1^{a_i}ciX0ai,diX1ai的话我们要求的就是 ∑i1k∑jik∏zijcz−∑i1k∑jik∏zijdz5\frac{\sum_{i1}^k\sum_{ji}^k\prod_{zi}^jc_z-\sum_{i1}^k\sum_{ji}^k\prod_{zi}^jd_z}{\sqrt 5}5∑i1k∑jik∏zijcz−∑i1k∑jik∏zijdz 这个好像看起来好维护一点不过首先我们要解决这个5\sqrt 55的问题因为其实5\sqrt 55在模998244353998244353998244353意义下是没有值的我们不能直接用二次剩余带入数字。
考虑维护一个类似于多项式的东西每个数字记为二元组(a,b)a5b(a,b)a\sqrt 5b(a,b)a5b。加减乘都很好搞除法的话需要推导一下 1a5bc5d\frac{1}{a\sqrt 5b}c\sqrt 5da5b1c5d 5ac5(adcb)bd15ac\sqrt 5(adcb)bd15ac5(adcb)bd1 5acbd1,adcb05acbd1,adcb05acbd1,adcb0 解出来c−ab2−5a2,dbb2−5a2c-\frac{a}{b^2-5a^2},d\frac{b}{b^2-5a^2}c−b2−5a2a,db2−5a2b 这样四则运算都搞定了可以开始考虑如何在LCTLCTLCT上面维护了。
类似线段树的设propropro表示所有数乘积pre/sufpre/sufpre/suf表示所有前/后缀乘积和ansansans表示我们维护的答案那么就可以合并两个东西了。LCTLCTLCT维护的时候顺便把单个的节点也合并进去就好了。
然后还剩下一个最麻烦的东西就是树链修改的时候我们需要快速算出连续xxx个uuu的信息。 propropro很好搞就是uxu^xuxsufsufsuf和preprepre就是一个简单的等比数列求和上通项公式就好了。 ansansans比较麻烦考虑每个uiu^iui的个数答案就是 ∑i1xui(x−i1)(x1)∑i1xui−∑i1xuii\sum_{i1}^xu^i(x-i1)(x1)\sum_{i1}^xu^i-\sum_{i1}^xu^iii1∑xui(x−i1)(x1)i1∑xui−i1∑xuii ⇒(x1)ux1−uu−1−xux1−ux−uu−1u−1\Rightarrow (x1)\frac{u^{x1}-u}{u-1}-\frac{xu^{x1}-\frac{u^x-u}{u-1}}{u-1}⇒(x1)u−1ux1−u−u−1xux1−u−1ux−u 这样就可以在logloglog时间复杂度以内合并了。
然后答案000次项一定是000的所以输出5\sqrt 55的项就好了。 时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includestack
#define ll long long
using namespace std;
const ll P998244353,N1e510;
struct node{ll a,b;//a带√5 node(ll aa0,ll bb0){aaa;bbb;return;}
};
ll power(ll x,ll bP-2){ll ans1;x%P;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
const node X((P1)/2,(P1)/2);
node operator(node x,node y)
{return node((x.ay.a)%P,(x.by.b)%P);}
node operator-(node x,node y)
{return node((x.a-y.a)%P,(x.b-y.b)%P);}
node operator*(node x,node y)
{return node((x.a*y.bx.b*y.a)%P,(x.b*y.b5*x.a*y.a)%P);}
node inv(node x){ll tmppower(x.b*x.b-5*x.a*x.a);return node(-x.a,x.b)*node(0,tmp);
}
node power(node x,ll b){node ans(0,1);while(b){if(b1)ansans*x;xx*x;b1;}return ans;
}
struct Tnode{node ans,pre,suf,pro;
};
Tnode operator(Tnode x,Tnode y){Tnode w;w.ansx.ansy.ansx.suf*y.pre;w.prex.prey.pre*x.pro;w.sufy.sufx.suf*y.pro;w.prox.pro*y.pro;return w;
}
struct SegTree{ll fa[N],t[N][2],siz[N];Tnode w[N];node v[N],lazy[N];bool r[N],hlz[N];stackll s;bool Nroot(ll x){return fa[x](t[fa[x]][0]x||t[fa[x]][1]x);}bool Direct(ll x){return t[fa[x]][1]x;}void Rev(ll x){swap(t[x][0],t[x][1]);swap(w[x].pre,w[x].suf);r[x]^1;return;}void PushUp(ll x){siz[x]siz[t[x][0]]siz[t[x][1]]1;w[x](Tnode){v[x],v[x],v[x],v[x]};if(t[x][0])w[x]w[t[x][0]]w[x];if(t[x][1])w[x]w[x]w[t[x][1]];return;}void Updata(ll x,node u){ll ssiz[x];lazy[x]v[x]u;node tmpinv(node(0,1)-u);hlz[x]1; w[x].propower(u,s);w[x].prew[x].suf(u-w[x].pro*u)*tmp;w[x].ans(node(0,s)-w[x].pre)*u*tmp;return;}void PushDown(ll x){if(hlz[x]){if(t[x][0])Updata(t[x][0],lazy[x]);if(t[x][1])Updata(t[x][1],lazy[x]);hlz[x]0;}if(!r[x])return;Rev(t[x][0]);Rev(t[x][1]);r[x]0;return;}void Rotate(ll x){ll yfa[x],zfa[y];ll xsDirect(x),ysDirect(y);ll wt[x][xs^1];if(Nroot(y))t[z][ys]x;t[x][xs^1]y;t[y][xs]w;if(w)fa[w]y;fa[y]x;fa[x]z;PushUp(y);PushUp(x);return;}void Splay(ll x){ll yx;s.push(x);while(Nroot(y))yfa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){ll yfa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(ll x){for(ll y0;x;yx,xfa[x])Splay(x),t[x][1]y,PushUp(x);return;}void MakeRoot(ll x){Access(x);Splay(x);Rev(x);return;}void Link(ll x,ll y){MakeRoot(1);Access(x);Splay(x);fa[t[x][0]]0;t[x][0]0;PushUp(x);fa[x]y;return;}ll Split(ll x,ll y){MakeRoot(x);Access(y);Splay(y);return (w[y].ans.aP)%P*2%P;}void Change(ll x,ll y,node val){MakeRoot(x);Access(y);Splay(y);Updata(y,val);return;}
}T;
ll n,m;
signed main()
{
// freopen(fibonacci.in,r,stdin);
// freopen(fibonacci.out,w,stdout);scanf(%lld%lld,n,m);for(ll i1;in;i){ll x;scanf(%lld,x);T.v[i]power(X,x);T.PushUp(i);}for(ll i2;in;i)scanf(%lld,T.fa[i]);while(m--){ll op,u,v,w;scanf(%lld,op);if(op1){scanf(%lld%lld,u,v);T.Link(u,v);}else if(op2){scanf(%lld%lld%lld,u,v,w);T.Change(u,v,power(X,w));}else if(op3){scanf(%lld,u);printf(%lld\n,T.Split(u,u));}else if(op4){scanf(%lld%lld,u,v);printf(%lld\n,T.Split(u,v));}}return 0;
}
