佛山网站建设怎么选,淘宝客优惠券网站建设教程,做网站域名的设置,做网站分辨率一般多少不知道这题能不能发出来#xff0c;如果不能请联系我#xff0c;我什么都会做的
题意#xff1a;给一棵 nnn 个结点的树#xff0c;每个结点有个 axbaxbaxb#xff0c;求所有根到叶子的乘积之和。系数模 998244353998244353998244353。
链的情况就是分治 NTT#xff0c…不知道这题能不能发出来如果不能请联系我我什么都会做的
题意给一棵 nnn 个结点的树每个结点有个 axbaxbaxb求所有根到叶子的乘积之和。系数模 998244353998244353998244353。
链的情况就是分治 NTT所以树上没有弱于这个的做法。
考虑链分治先对树做长链剖分然后对根所在的链分治维护两个多项式一个链上所有结点的乘积一个从区间起点往下走从区间中某个位置拐出去走到所有叶子的路径乘积之和。递归到分治树的叶子的时候就递归算原树上的轻儿子。
为了保证复杂度NTT 的长度应该开当前区间所有虚儿子的最大深度和区间长度的较大值而非区间起点的深度。这样每条链只会在链头的父亲所在的链 分治的时候贡献 O(logn)\Omicron(\log n)O(logn) 次 NTT 的长度总复杂度是 O(nlog2n)\Omicron(n\log^2n)O(nlog2n)并且上界很松。
第一次写封装多项式挺舒服的
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#define MAXN ((118)5)
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
const int MOD998244353;
typedef long long ll;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD,p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
int rt[2][24];
int r[MAXN],l,lim;
inline void init(){lim1l;for (int i0;ilim;i) r[i](r[i1]1)|((i1)(l-1));}
void ntt(int* a,int type)
{for (int i0;ilim;i) if (ir[i]) swap(a[i],a[r[i]]);for (int L0;Ll;L){int mid1L,lenmid1;int Wnrt[type][L1];for (int s0;slim;slen){ll w1;for (int k0;kmid;k,ww*Wn%MOD){int xa[sk],yw*a[smidk]%MOD;a[sk]add(x,y),a[smidk]dec(x,y);}}}if (type){int tinv(lim);for (int i0;ilim;i) a[i](ll)a[i]*t%MOD;}
}
struct poly
{int *a,n;inline poly():n(0){}inline poly(int x):n(x){anew int[x];memset(a,0,sizeof(int)*n);}inline poly(int x,int y):n(2){anew int[2];a[0]x,a[1]y;}inline int operator [](const int i){return a[i];}inline const int operator [](const int i)const{return a[i];}
};
inline poly operator *(const poly a,const poly b)
{static int ta[MAXN],tb[MAXN];poly c(a.nb.n-1);for (l0;(1l)c.n;l);init();for (int i0;ilim;i) ta[i]tb[i]0;for (int i0;ia.n;i) ta[i]a[i];for (int i0;ib.n;i) tb[i]b[i];ntt(ta,0),ntt(tb,0);for (int i0;ilim;i) ta[i](ll)ta[i]*tb[i]%MOD;ntt(ta,1);for (int i0;ic.n;i) c[i]ta[i];return c;
}
inline poly operator (const poly a,const poly b)
{poly c(max(a.n,b.n));for (int i0;ic.n;i) c[i]add(ia.n? a[i]:0,ib.n? b[i]:0);return c;
}
vectorint e[MAXN];
int buf[MAXN],*tpbuf;
int fa[MAXN],son[MAXN],mx[MAXN];
int *lis[MAXN];
inline int* newbuf(int x){int* ptp;tpx;return p;}
void dfs(int u,int f)
{fa[u]f;for (int i0;i(int)e[u].size();i)if (e[u][i]!f){dfs(e[u][i],u);if (mx[e[u][i]]mx[son[u]]) son[u]e[u][i];}mx[u]mx[son[u]]1;
}
void dfs(int u,int* cur)
{*(lis[u]cur)u;if (son[u]) dfs(son[u],cur1);for (int i0;i(int)e[u].size();i)if (e[u][i]!fa[u]e[u][i]!son[u])dfs(e[u][i],newbuf(mx[e[u][i]]));
}
int rval[MAXN],gval[MAXN];
pairpoly,poly solve(int* L,int* R)
{if (LR){int u*L;poly tmp;for (int i0;i(int)e[u].size();i)if (e[u][i]!fa[u]e[u][i]!son[u])tmptmpsolve(lis[e[u][i]],lis[e[u][i]]mx[e[u][i]]-1).second;if ((int)e[u].size()(fa[u]0)) tmppoly(1),tmp[0]1;return make_pair(poly(rval[u],gval[u]),poly(rval[u],gval[u])*tmp);}int* midL((R-L)1);pairpoly,poly lanssolve(L,mid),ranssolve(mid1,R);return make_pair(lans.first*rans.first,lans.first*rans.secondlans.second);
}
poly ans;
int main()
{freopen(slime.in,r,stdin);freopen(slime.out,w,stdout);rt[0][23]qpow(3,119),rt[1][23]inv(rt[0][23]);for (int i22;i0;i--){rt[0][i](ll)rt[0][i1]*rt[0][i1]%MOD;rt[1][i](ll)rt[1][i1]*rt[1][i1]%MOD;}int nread();read();for (int i1;in;i) rval[i]read();for (int i1;in;i) gval[i]read();for (int i1;in;i){int u,v;uread(),vread();e[u].push_back(v),e[v].push_back(u);}dfs(1,0);dfs(1,newbuf(mx[1]));anssolve(lis[1],lis[1]mx[1]-1).second;for (int i0;in;i) printf(%d\n,(ians.n? ans[i]:0));return 0;
}
