网站首页优化公司,wordpress会员计时,十大最耐看装修风格,小程序电商系统开发题意#xff1a;nnn 个点的带点权的树#xff0c;点权最大值为 www#xff0c;求所有连通子图第 kkk 大权值之和模 641236412364123。 n,w≤1666n,w\leq 1666n,w≤1666#xff0c;时限 5s。
idea 很好的题#xff0c;可惜被暴力艹过去了。
首先如果点权只有 000 和 111nnn 个点的带点权的树点权最大值为 www求所有连通子图第 kkk 大权值之和模 641236412364123。
n,w≤1666n,w\leq 1666n,w≤1666时限 5s。
idea 很好的题可惜被暴力艹过去了。
首先如果点权只有 000 和 111我们相当于求包含至少 kkk 个 111 的连通子图个数。可以设 f(u,k)f(u,k)f(u,k) 表示 uuu 为根的可空连通子图中有恰好 kkk 个 111 的数量然后就是刻在 DNA 里的转移方程
f(u,k)⟵∑i0kf(u,i)g(v,k−i)f(u,k)\longleftarrow\sum_{i0}^kf(u,i)g(v,k-i)f(u,k)⟵i0∑kf(u,i)g(v,k−i)
f(u,0)⟵f(u,0)1f(u,0)\longleftarrow f(u,0)1f(u,0)⟵f(u,0)1
边界 f(u,valu)1f(u,val_u)1f(u,valu)1
我们枚举值域大于等于的设为 111小于的设为 000算出方案数乘上差值就可以 O(n2w)\Omicron(n^2w)O(n2w) 踩标算了。
注意到这个转移方程是卷积的形式所以可以写成生成函数
fu(x)∏v∈son(u)fv(x)1f_u(x)\prod_{v\in son(u)}f_v(x)1fu(x)v∈son(u)∏fv(x)1
然后你要求所有点的和所以开个 ggg 顺便记一下
gu(x)∑v∈son(u)gv(x)fu(x)−1g_u(x)\sum_{v\in son(u)}g_v(x)f_u(x)-1gu(x)v∈son(u)∑gv(x)fu(x)−1
所有的生成函数都是 nnn 次的所以考虑带 n1n1n1 个点值进去算。因为不是 NTT 模数所以只能带一般的点值最后再插值回来。
这样还是 O(n2w)\Omicron(n^2w)O(n2w) 的。带点值这步不好优化但后面的枚举值域看起来可以优化一下。
可以动态 dp但常数巨大还没暴力跑得快。
注意到不同的阀值的计算过程是一样的可以考虑用线段树合并维护所有阀值的答案。
开个长度为值域的线段树我们在线段树的每个叶子记录这个阀值的 (f,g)(f,g)(f,g)初值为 (0,0)(0,0)(0,0)。你需要维护以下操作
开头的 fff 区间加和区间乘。合并两棵线段树fff 对应位置相乘 ggg 对应位置相加。最后的 f←f1,g←gff\leftarrow f1,g\leftarrow gff←f1,g←gf。
手玩一个标记 (a,b,c,d)(a,b,c,d)(a,b,c,d) 表示 (f,g)⟵(afb,cfgd)(f,g)\longleftarrow (afb,cfgd)(f,g)⟵(afb,cfgd)就可以做了。
关于有懒标记的线段树合并线段树合并的过程中两边有一边没有儿子时直接返回这样 pushdown 次数和递归次数同阶不影响复杂度。
最后插值即可。
复杂度 O(wnlogw)\Omicron(wn\log w )O(wnlogw)
#include iostream
#include cstring
#include cctype
#include cstdio
#include vector
#include algorithm
#define MAXN 2005
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 MOD64123;
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;}
vectorint e[MAXN];
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;
}
struct data
{int a,b,c,d;inline data(const int a1,const int b0,const int c0,const int d0):a(a),b(b),c(c),d(d){}
};
inline data operator *(const data x,const data y){return data((ll)x.a*y.a%MOD,((ll)y.a*x.by.b)%MOD,((ll)x.a*y.cx.c)%MOD,((ll)x.b*y.cx.dy.d)%MOD);}
int n,k,w,val[MAXN];
int ch[MAXN5][2],cnt;
data tag[MAXN5];
inline void clear()
{for (int i1;icnt;i) ch[i][0]ch[i][1]0,tag[i]data();cnt0;
}
inline void pushtag(int x,const data v){tag[x]tag[x]*v;}
inline void pushdown(int x)
{if (!ch[x][0]) ch[x][0]cnt;if (!ch[x][1]) ch[x][1]cnt;pushtag(ch[x][0],tag[x]),pushtag(ch[x][1],tag[x]);tag[x]data();
}
int merge(int x,int y)
{if (!x||!y) return x|y;if (!ch[x][0]!ch[x][1]) swap(x,y);if (!ch[y][0]!ch[y][1]){tag[x]tag[x]*data(tag[y].b,0,0,0);tag[x]tag[x]*data(1,0,0,tag[y].d);return x;}pushdown(x),pushdown(y);ch[x][0]merge(ch[x][0],ch[y][0]);ch[x][1]merge(ch[x][1],ch[y][1]);return x;
}
void modify(int x,int l,int r,int ql,int qr,data v)
{if (!x) xcnt;if (qllrqr) return pushtag(x,v);if (qrl||rql) return;int mid(lr)1;pushdown(x);modify(ch[x][0],l,mid,ql,qr,v),modify(ch[x][1],mid1,r,ql,qr,v);
}
int querysum(int x,int l,int r)
{if (lr) return tag[x].d;int mid(lr)1;pushdown(x);return add(querysum(ch[x][0],l,mid),querysum(ch[x][1],mid1,r));
}
int rt[MAXN];
void dfs(int u,int f,int v)
{modify(rt[u],1,w,1,w,data(0,1,0,0));modify(rt[u],1,w,1,val[u],data(v,0,0,0));for (int i0;i(int)e[u].size();i)if (e[u][i]!f){dfs(e[u][i],u,v);rt[u]merge(rt[u],rt[e[u][i]]);}modify(rt[u],1,w,1,w,data(1,1,1,0));
}
int calc(int v)
{clear();for (int i1;in;i) rt[i]0;dfs(1,0,v);return querysum(rt[1],1,w);
}
int ans[MAXN],s[MAXN],tmp[MAXN],f[MAXN];
int main()
{nread(),kread(),wread();for (int i1;in;i) val[i]read();for (int i1;in;i){int u,v;uread(),vread();e[u].push_back(v),e[v].push_back(u);}for (int v1;vn1;v)ans[v]calc(v);s[0]1;for (int i1;in1;i){for (int ji;j1;j--)s[j]dec(s[j-1],(ll)i*s[j]%MOD); s[0](ll)s[0]*(MOD-i)%MOD;}for (int i1;in1;i){int xans[i];for (int j1;jn1;j) if (i!j) x(ll)x*qpow(dec(i,j),MOD-2)%MOD;tmp[0](ll)s[0]*qpow(MOD-i,MOD-2)%MOD;for (int j1;jn1;j) tmp[j](ll)dec(tmp[j-1],s[j])*qpow(i,MOD-2)%MOD;for (int j0;jn1;j) f[j](f[j](ll)x*tmp[j])%MOD;}int res0;for (int ik;in;i) resadd(res,f[i]);coutres;return 0;
}
