2020-2021:teams:legal_string:组队训练比赛记录:缓冲区
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/22 15:29] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ===== A. A Math Challenge ===== | + | ===== H. travel ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | 给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。 | ||
| + | |||
| + | 我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。 | ||
| + | |||
| + | 如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。 | ||
| + | |||
| + | 考虑状态转移，利用生成链的合并，不难有 | ||
| $$ | $$ | ||
| - | \sum_{i=0}^n\sum_{1\le cj\le ai+b}i^pj^q | + | \text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\ |
| + | \text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\ | ||
| + | \text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\ | ||
| + | \text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\ | ||
| + | \text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j) | ||
| $$ | $$ | ||
| - | ==== 题解 ==== | + | 注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。 |
| - | 设 $F(n)=\sum_{i=1}^n i^q$，于是上式转化为 | + | 初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有 |
| $$ | $$ | ||
| - | \sum_{i=0}^ni^pF(\lfloor \frac {ai+b}c\rfloor) | + | \text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1)) |
| $$ | $$ | ||
| - | 由于 $F(n)$ 是 $q+1$ 次多项式，所以高斯消元可以暴力求出 $F(n)$ 的表达式。于是问题转化为计算 $\sum_{i=0}^ni^p(\lfloor \frac {ai+b}c\rfloor)^k(0\le k\le q)$。 | + | 最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。 |
| - | 上式用万能欧几里得算法板子可以 $O\left(p^2q^2\log c\right)$，题目正解是类欧几里得算法 $O\left((p+q)^3\log c\right)$，不过卡卡常还是能过的。 | + | [[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]] |
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | const int mod=998244353,MAXK=53; | + | const int MAXN=4e5+5,MAXK=4; |
| - | int C[MAXK][MAXK]; | + | struct Edge{ |
| - | struct Node{ | + | int to,next; |
| - | int cntr,cntu,f[MAXK][MAXK]; | + | }edge[MAXN<<1]; |
| - | Node(int cntr=0,int cntu=0){ | + | int a[MAXN],head[MAXN],edge_cnt; |
| - | this->cntr=cntr; | + | LL dp[MAXN][3][MAXK],tmp[3][MAXK]; |
| - | this->cntu=cntu; | + | void Insert(int u,int v){ |
| - | mem(f,0); | + | edge[++edge_cnt]=Edge{v,head[u]}; |
| - | } | + | head[u]=edge_cnt; |
| - | Node operator * (const Node &b)const{ | + | |
| - | static int px[MAXK],py[MAXK]; | + | |
| - | static int b1[MAXK][MAXK],b2[MAXK][MAXK]; | + | |
| - | Node c; | + | |
| - | int dx=cntr,dy=cntu; | + | |
| - | px[0]=py[0]=1; | + | |
| - | _for(i,1,MAXK) | + | |
| - | px[i]=1LL*px[i-1]*dx%mod; | + | |
| - | _for(i,1,MAXK) | + | |
| - | py[i]=1LL*py[i-1]*dy%mod; | + | |
| - | _for(i,0,MAXK)_rep(j,0,i){ | + | |
| - | b1[i][j]=1LL*C[i][j]*px[i-j]%mod; | + | |
| - | b2[i][j]=1LL*C[i][j]*py[i-j]%mod; | + | |
| - | } | + | |
| - | c.cntr=(cntr+b.cntr)%mod; | + | |
| - | c.cntu=(cntu+b.cntu)%mod; | + | |
| - | _for(i,0,MAXK)_for(j,0,MAXK){ | + | |
| - | c.f[i][j]=f[i][j]; | + | |
| - | _rep(i2,0,i)_rep(j2,0,j) | + | |
| - | c.f[i][j]=(c.f[i][j]+1LL*b.f[i2][j2]*b1[i][i2]%mod*b2[j][j2])%mod; | + | |
| - | } | + | |
| - | return c; | + | |
| - | } | + | |
| - | }; | + | |
| - | Node quick_pow(Node n,int k){ | + | |
| - | Node ans=Node(0,0); | + | |
| - | while(k){ | + | |
| - | if(k&1)ans=ans*n; | + | |
| - | k>>=1; | + | |
| - | if(k)n=n*n; | + | |
| - | } | + | |
| - | return ans; | + | |
| } | } | ||
| - | Node asgcd(int a,int b,int c,int n,Node su,Node sr){ | + | void Max(LL &a,LL b){ |
| - | if(a>=c) | + | if(b>a) |
| - | return asgcd(a%c,b,c,n,su,quick_pow(su,a/c)*sr); | + | a=b; |
| - | int m=(1LL*a*n+b)/c; | + | |
| - | if(!m) | + | |
| - | return quick_pow(sr,n); | + | |
| - | else | + | |
| - | return quick_pow(sr,(c-b-1)/a)*su*asgcd(c,(c-b-1)%a,a,m-1,sr,su)*quick_pow(sr,n-(1LL*c*m-b-1)/a); | + | |
| } | } | ||
| - | Node cal(int a,int b,int c,int n){ | + | void dfs(int u,int fa){ |
| - | Node su=Node(0,1),sr=Node(1,0); | + | dp[u][1][0]=a[u]; |
| - | _for(i,0,MAXK) | + | for(int i=head[u];i;i=edge[i].next){ |
| - | sr.f[i][0]=1; | + | int v=edge[i].to; |
| - | return quick_pow(su,b/c)*asgcd(a,b%c,c,n,su,sr); | + | if(v==fa)continue; |
| - | } | + | dfs(v,u); |
| - | int a[MAXK][MAXK],pw[MAXK][MAXK],A[MAXK]; | + | _for(i,0,3)_for(j,0,MAXK) |
| - | void Init(){ | + | tmp[i][j]=dp[u][i][j]; |
| - | C[0][0]=1; | + | _for(i,0,MAXK)_for(j,0,MAXK-i){ |
| - | _for(i,1,MAXK){ | + | Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]); |
| - | C[i][0]=1; | + | Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]); |
| - | _rep(j,1,i) | + | Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]); |
| - | C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; | + | Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]); |
| - | } | + | Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]); |
| - | _for(i,0,MAXK){ | + | |
| - | pw[i][0]=1; | + | |
| - | _for(j,1,MAXK) | + | |
| - | pw[i][j]=1LL*pw[i][j-1]*i%mod; | + | |
| - | } | + | |
| - | } | + | |
| - | int quick_pow(int n,int k){ | + | |
| - | int ans=1; | + | |
| - | while(k){ | + | |
| - | if(k&1)ans=1LL*ans*n%mod; | + | |
| - | n=1LL*n*n%mod; | + | |
| - | k>>=1; | + | |
| - | } | + | |
| - | return ans; | + | |
| - | } | + | |
| - | void build(int n){ | + | |
| - | _for(i,0,n){ | + | |
| - | _for(j,0,n) | + | |
| - | a[i][j]=pw[i][j]; | + | |
| - | _rep(j,1,i) | + | |
| - | a[i][n]=(a[i][n]+pw[j][n-2])%mod; | + | |
| - | } | + | |
| - | _for(i,0,n){ | + | |
| - | int pos=-1; | + | |
| - | _for(j,i,n){ | + | |
| - | if(a[j][i]){ | + | |
| - | pos=j; | + | |
| - | break; | + | |
| - | } | + | |
| - | } | + | |
| - | if(pos!=i) | + | |
| - | swap(a[i],a[pos]); | + | |
| - | int div=quick_pow(a[i][i],mod-2); | + | |
| - | _rep(j,i,n) | + | |
| - | a[i][j]=1LL*a[i][j]*div%mod; | + | |
| - | _rep(j,0,n){ | + | |
| - | if(j==i)continue; | + | |
| - | for(int k=n;k>=i;k--) | + | |
| - | a[j][k]=(a[j][k]+mod-1LL*a[j][i]*a[i][k]%mod)%mod; | + | |
| } | } | ||
| + | _for(i,0,3)_for(j,0,MAXK) | ||
| + | dp[u][i][j]=tmp[i][j]; | ||
| } | } | ||
| - | _for(i,0,n) | + | _for(i,1,MAXK) |
| - | A[i]=a[i][n]; | + | Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1])); |
| } | } | ||
| int main() | int main() | ||
| { | { | ||
| - | Init(); | + | int n=read_int(); |
| - | int a=read_int(),b=read_int(),c=read_int(),p=read_int(),q=read_int(),n=read_int(); | + | _rep(i,1,n) |
| - | Node ans=cal(a,b,c,n); | + | a[i]=read_int(); |
| - | int base=1; | + | _for(i,1,n){ |
| - | _for(i,0,MAXK){ | + | int u=read_int(),v=read_int(); |
| - | ans.f[0][i]=(ans.f[0][i]+base)%mod; | + | Insert(u,v); |
| - | base=1LL*base*(b/c)%mod; | + | Insert(v,u); |
| } | } | ||
| - | build(q+2); | + | dfs(1,0); |
| - | int s=0; | + | enter(dp[1][0][3]); |
| - | _rep(i,0,q+1) | + | |
| - | s=(s+1LL*ans.f[p][i]*A[i])%mod; | + | |
| - | enter(s); | + | |
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/缓冲区.1629617385.txt.gz · 最后更改: 2021/08/22 15:29 由 jxm2001
