【学习笔记】[AGC063E] Child to Parent

news/2024/2/25 14:07:20/文章来源:https://blog.csdn.net/cqbzlydd/article/details/135633089

提供一个多项式做法。

分别设 f u , i , g u , i f_{u,i},g_{u,i} fu,i,gu,i表示以 u u u为根时, a u = i a_u=i au=i a u ≥ i a_u\ge i aui的方案数,合并子树 v v v时,转移如下:

f u , i = ∑ f u , i − k r × g v . k f_{u,i}=\sum f_{u,i-kr}\times g_{v.k} fu,i=fu,ikr×gv.k

初值为 f u , a u = 1 f_{u,a_u}=1 fu,au=1

注意到 DP 的值域很大,通常情况下我们可以考虑用拉格朗日插值法来处理,但是实际上只要满足信息封闭也是可以转移的。我们不妨将其转化成多项式的形式,从而来观察需要记录哪些信息。

设:
F u ( x ) = ∑ f u , i x i G u ( x ) = ∑ g u , i x i F_u(x)=\sum f_{u,i}x^i\\G_u(x)=\sum g_{u,i}x^i Fu(x)=fu,ixiGu(x)=gu,ixi

转移大致分为以下几步:

F u ( x ) ← ∏ G v ( x ) F u ( x ) ← x a i F u ( x r ) G u ( x ) ← F u ( x ) + F u ( 1 ) − F u ( x ) 1 − x F_u(x)\gets \prod G_v(x)\\F_u(x)\gets x^{a_i}F_u(x^r)\\ G_u(x)\gets F_u(x)+\frac{F_u(1)-F_u(x)}{1-x} Fu(x)Gv(x)Fu(x)xaiFu(xr)Gu(x)Fu(x)+1xFu(1)Fu(x)

其中最后一个式子是在求后缀和,之所以不能写成 1 1 − x − 1 \frac{1}{1-x^{-1}} 1x11的原因是生成函数不能有次数 < 0 <0 <0的项。

现在问题在于,要求出 F u ( 1 ) F_u(1) Fu(1)就必须维护各项系数,显然次数太高就寄了。考虑一步非常巧妙的转化:我们设 G u ′ ( x ) = G u ( x + 1 ) , F u ′ ( x ) = F u ( x + 1 ) G'_u(x)=G_u(x+1),F'_u(x)=F_u(x+1) Gu(x)=Gu(x+1),Fu(x)=Fu(x+1),则 F u ′ ( 0 ) = F u ( 1 ) F'_u(0)=F_u(1) Fu(0)=Fu(1),而 F u ′ ( 0 ) F'_u(0) Fu(0)其实就是常数项,又因为要求的答案也是常数项,这样我们只用算次数较低的项,信息就封闭了。

新的转移大致为:

F u ′ ( x ) ← ∏ G v ′ ( x ) F'_u(x)\gets \prod G'_v(x)\\ Fu(x)Gv(x)

这是因为

F u ′ ( x ) = F u ( x + 1 ) = ∏ G v ( x + 1 ) = ∏ G v ′ ( x ) F'_u(x)=F_u(x+1)=\prod G_v(x+1)=\prod G'_v(x) Fu(x)=Fu(x+1)=Gv(x+1)=Gv(x)

F u ′ ( x ) ← ( x + 1 ) a i F u ′ ( ( x + 1 ) r − 1 ) F_u'(x)\gets (x+1)^{a_i}F_u'((x+1)^r-1) Fu(x)(x+1)aiFu((x+1)r1)

这是因为

F u ′ ( x ) = F u ( x + 1 ) = ( x + 1 ) a i F u ( ( x + 1 ) r ) = ( x + 1 ) a i F u ′ ( ( x + 1 ) r − 1 ) F'_u(x)=F_u(x+1)=(x+1)^{a_i}F_u((x+1)^r)=(x+1)^{a_i}F_u'((x+1)^r-1) Fu(x)=Fu(x+1)=(x+1)aiFu((x+1)r)=(x+1)aiFu((x+1)r1)

G u ′ ( x ) = F u ′ ( x ) + F u ′ ( 0 ) − F u ′ ( x ) − x G'_u(x)=F'_u(x)+\frac{F'_u(0)-F'_u(x)}{-x} Gu(x)=Fu(x)+xFu(0)Fu(x)

如果我们只保留前 k k k项,那么因为要除以 x x x,所以每次转移完后最后一项都会损失掉。但是因为答案是第一项的值,所以我们对于每个节点保留 d e p u dep_u depu项即可。

复杂度 O ( n 3 ) O(n^3) O(n3)

麻了,好像和官方题解长得一样。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int mod=998244353;
int n,fa[305],dep[305];
ll r,fac[305],inv[305],ifac[305],to[305][305],f[305][305],g[305][305],a[305],res;
vector<int>G[305];
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
ll binom(int x,int y){if(x<0||y<0||x<y)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;ifac[1]=1;for(int i=2;i<=n;i++)ifac[i]=mod-ifac[mod%i]*(mod/i)%mod;
}
void dfs(int u){f[u][0]=1;for(auto v:G[u]){dep[v]=dep[u]+1,dfs(v);memset(f[0],0,sizeof f[0]);for(int i=0;i<=dep[v];i++)for(int j=0;i+j<=dep[v];j++)(f[0][i+j]+=f[u][i]*g[v][j])%=mod;memcpy(f[u],f[0],sizeof f[0]);}memset(f[0],0,sizeof f[0]);for(int i=0;i<=dep[u]+1;i++)for(int j=0;j<=dep[u]+1;j++)(f[0][j]+=f[u][i]*to[i][j])%=mod;memset(f[u],0,sizeof f[u]);ll mul=1;for(int i=0;i<=dep[u]+1;i++){for(int j=0;i+j<=dep[u]+1;j++)(f[u][i+j]+=mul*f[0][j])%=mod;mul=mul*(a[u]-i)%mod*ifac[i+1]%mod;}for(int i=0;i<=dep[u];i++)g[u][i]=(f[u][i]+f[u][i+1])%mod;
}
signed main(){//freopen("data.in","r",stdin);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=2;i<=n;i++)cin>>fa[i],G[fa[i]].pb(i);cin>>r;init(n);to[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=i;j++){ll mul=1;int sgn=(i-j&1)?-1:1;for(int k=0;k<=n;k++){(to[i][k]+=sgn*binom(i,j)*mul)%=mod;mul=mul*((j*r-k)%mod)%mod*ifac[k+1]%mod;}}}for(int i=1;i<=n;i++)cin>>a[i];dfs(1);cout<<(f[1][0]+mod)%mod;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925726.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2024年腾讯云主机价格表,附报价明细

腾讯云服务器租用价格表&#xff1a;轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、轻量4核8G12M服务器446元一年、646元15个月&#xff0c;云服务器CVM S5实例2核2G配置280.8元一年…

机器学习小记——KNN(K近邻)

为了让绝大多数人都可以看懂&#xff0c;所以我就用简单的话语来讲解机器学习每一个算法 第一次写ML的博文&#xff0c;所以可能会有些地方出错&#xff0c;欢迎各位大佬提出意见或错误 祝大家开心进步每一天&#xff5e; 博文代码全部为python 简单的说一下什么是机器学习…

adb wifi 远程调试 安卓手机 命令

使用adb wifi 模式调试需要满足以下前提条件&#xff1a; 手机 和 PC 需要在同一局域网下。手机需要开启开发者模式&#xff0c;然后打开 USB 调试模式。 具体操作步骤如下&#xff1a; 将安卓手机通过 USB 线连接到 PC。&#xff08;连接的时候&#xff0c;会弹出请求&#x…

Android 系统启动过程纪要(基于Android 10)

前言 看过源码的都知道&#xff0c;Launcher系统启动都会经过这三个进程 init ->zygote -> system_server。今天我们就来讲解一下这三个进程以及Launcher系统启动。 init进程 准备Android虚拟机环境&#xff1a;创建和挂载系统文件目录&#xff1b;初始化属性服务&…

AI大模型预先学习笔记二:prompt提问大模型、langchain使用大模型框架、fine tune微调大模型

文章目录 一、Prompt Engineering&#xff08;怎么去提问大模型&#xff09;1&#xff09;环境准备2&#xff09;交互代码的参数备注3&#xff09;交互代码 二、LangChain&#xff08;一个框架去使用大模型&#xff09;1&#xff09;LangChain核心介绍&#xff1a;I/O模块、数据…

Java NIO (二)NIO Buffer类的重要方法

1 allocate()方法 在使用Buffer实例前&#xff0c;我们需要先获取Buffer子类的实例对象&#xff0c;并且分配内存空间。需要获取一个Buffer实例对象时&#xff0c;并不是使用子类的构造器来创建&#xff0c;而是调用子类的allocate()方法。 public class AllocateTest {static…

四、Sharding-JDBC系列04:分库分表后,如何不停机迁移数据?

目录 停机迁移方案 双写迁移方案 一般会有两种方案&#xff1a; 停机迁移方案 这种方案最简单也是最low的。 数据迁移前&#xff0c;在网站或者app挂个公告&#xff0c;说0点到早上6点系统进行维护&#xff0c;无法访问。 接着到0点停机&#xff0c;系统停掉&#xff0c;…

k8s---配置资源管理

目录 配置资源管理的方式 secret pod如何来引用secret&#xff1f;&#xff1f;&#xff1f; 陈述式创建&#xff1a; 声明式创建 Secret创建加密文件 使用token挂载 环境变量使用 docker-registry ConfigMap 陈述式 热更新 总结&#xff1a; 配置资源管理的方式 …

Go-gin-example 第二部分 jwt验证

文章目录 使用 JWT 进行身份校验jwt知识点补充认识JWTTOKEN是什么jwt的使用场景jwt的组成headerpayloadsignature 下载依赖包编写 jwt 工具包jwt中间件编写如何获取token 编写获取token的Apimodels逻辑编写路由逻辑编写修改路由逻辑 验证token将中间件接入Gin功能验证模块 续接…

【开源】基于JAVA语言的固始鹅块销售系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 鹅块类型模块2.3 固始鹅块模块2.4 鹅块订单模块2.5 评论管理模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 鹅块类型表3.2.2 鹅块表3.2.3 鹅块订单表3.2.4 鹅块评论表 四、系统展示五、核心代码5.…

FPGA之初探

FPGA的构成 基本逻辑单元CLB CLB是FPGA的基本逻辑单元&#xff0c; 一个 CLB 包括了 2 个 Slices&#xff0c;所以知道Slices的数量就可以知道FPGA的“大概”逻辑资源容量了。一个 Slice 等于 4 个6输入LUT8个触发器(flip-flop)算数运算逻辑&#xff0c;每个 Slice 的 4 个触发…

[足式机器人]Part2 Dr. CAN学习笔记-Advanced控制理论 Ch04-17 串讲

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记-Advanced控制理论 Ch04-17 串讲

Komodor:Kubernetes 监控工具全面指南

为了方便起见&#xff0c;Komodor 提供了一个简单的 Web 界面&#xff0c;以帮助您监控 Kubernetes 集群的状态。它拥有付费和免费增值计划&#xff0c;除了在出现问题时通知用户外&#xff0c;还拥有一系列方便的工具&#xff0c;用于跟踪和管理集群中部署的资源的状态。让我们…

如何用GPT进行论文润色与改写?

详情点击链接&#xff1a;如何用GPT进行论文润色与改写&#xff1f; 一OpenAI 1.最新大模型GPT-4 Turbo 2.最新发布的高级数据分析&#xff0c;AI画图&#xff0c;图像识别&#xff0c;文档API 3.GPT Store 4.从0到1创建自己的GPT应用 5. 模型Gemini以及大模型Claude2二定…

逻辑回归(解决分类问题)

定义&#xff1a;逻辑回归是一种用于解决分类问题的统计学习方法。它通过对数据进行建模&#xff0c;预测一个事件发生的概率。逻辑回归通常用于二元分类问题&#xff0c;即将数据分为两个类别。它基于线性回归模型&#xff0c;但使用了逻辑函数&#xff08;也称为S形函数&…

MR-GCN

∘ Φ \circ_Φ ∘Φ​ denotes a convolution Let b l o c k d i a g blockdiag blockdiag(A) be a n1n3-by-n2n3 block diagonal matrix&#xff0c; f o l d fold fold indicate its inverse operator diagonal degree tensor D \mathcal{D} D 作者未提供代码

【学习心得】Git深入学习

若您还未安装Git或是只想简单使用&#xff0c;可以先看看我的文章“Git快速上手”【学习心得】Git快速上手http://t.csdnimg.cn/gsaGj 一、深入学习Git必须熟悉两个概念 &#xff08;1&#xff09;【四个区】Git本地有三个区&#xff0c;远程仓库也可以看出成一个区域 工作区…

vtk9.3 + Visual Studio2019 + Cmake3.28 win11 上的环境安装(这个过程网上比较多,自己记录下过程加深下印象)

开始 介绍 欢迎来到 VTK&#xff01;我们建议您首先阅读《VTK book》&#xff0c;这是一本全面的 VTK 指南&#xff0c;涵盖了其功能的所有方面。此外&#xff0c;您可能会发现探索 VTK 示例很有帮助&#xff0c;这是一组有用的参考资料&#xff0c;演示了如何使用 VTK 的不同模…

ASP.NET Core 的 Web Api 实现限流 中间件

Microsoft.AspNetCore.RateLimiting 中间件提供速率限制&#xff08;限流&#xff09;中间件。 它是.NET 7 以上版本才支持的中间件&#xff0c;刚看了一下&#xff0c;确实挺好用&#xff0c;下面给大家简单介绍一下&#xff1a; RateLimiterOptionsExtensions 类提供下列用…

Elasticsearch 7.8.0从入门到精通

安装Elasticsearch 7.8.0 官网&#xff1a;Elasticsearch 7.8.0 | Elastic 大家下载所需要的安装包即可。然后解压缩&#xff1a; Elasticsearch是通过java编写的&#xff0c;所以自带jdk。多好&#xff0c;下载Elasticsearch赠送jdk 0.0&#xff0c;不过一般我们用自己的jdk…