点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp:0922T4

2023-10-25 14:10

本文主要是介绍点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp:0922T4,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

首先连通块,所以点分治肯定是

Trick1 钦定选根的连通块dp

对于钦定选根的连通块dp,有一种常见思路

先对原树求其dfn序,按dfn序倒序求解

具体的,对于当前点 i i i(注意这里都是指dfn序),我们可以钦定 i i i 是否选

如果 i i i 选,就由 i + 1 i+1 i+1,也就是 i i i 的第一个儿子转移过来(因为只有他选他子树才可能被选)

如果 i i i 不选,就由 i + w i i+w_i i+wi 转移过来,因为他的儿子必然不会被选

至于 i i i i + w i i+w_i i+wi 同时选的情况,我们在 i + 1 i+1 i+1 那里已经算了

对于 i i i i + w i i+w_i i+wi 是否连通的问题,当他们的lca都被选时,则他们必然也被选,这里一定会在他们祖先那里被算到

在这里插入图片描述

Trick 2 对于乘积类dp的根号优化方法

考虑直接 d p [ x ] [ i ] dp[x][i] dp[x][i] i i i 值域过大。

但我们可以拆分 f ( x , i ) , g ( x , i ) f(x,i),g(x,i) f(x,i),g(x,i),代表已选乘积为 i i i / 还可以选乘积为 i i i 的方案数

这样状态直接压成 O ( m ) O(\sqrt m) O(m )

其实也可以用整除分块的证明进行预处理

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 4010
#define M 1510
#define mo (int)(1e9+7)
int n, m, i, j, k, T;
int Rt, rt, f[N][M], g[N][M]; 
int mx[N], w[N], dfn[N], tot, sum,  u, v; 
int sq, p[N], v1, v2, a[N], ans; 
vector<int>G[N]; void dfs(int x, int fa) {w[x]=mx[x]=1; for(int y : G[x]) {if(y==fa || p[y]) continue; dfs(y, x); w[x]+=w[y]; mx[x]=max(mx[x], w[y]); }mx[x]=max(mx[x], sum-w[x]); if(mx[x]<mx[rt]) rt=x; 
}void dfs2(int x, int fa) {dfn[++tot]=x;  for(int y: G[x]) if(y!=fa && !p[y]) dfs2(y, x); 
}void Add(int &a, int b) {a=(a+b)%mo; 
}void dfz(int x) {
//	printf("> %lld\n", x); int i, j, u; tot=0; dfs(x, 0); dfs2(x, 0); 
//	for(i=1; i<=tot; ++i) printf("%lld ", dfn[i]); printf("\n"); for(i=0; i<=tot+5; ++i)for(j=0; j<=sq+5; ++j) f[i][j]=g[i][j]=0; 
//	f[tot+1][1]=1; for(i=tot; i>=1; --i) {u=dfn[i]; if(a[u]>sq) Add(g[i][m/a[u]], 1); else Add(f[i][a[u]], 1); for(j=1; j<=sq; ++j) {v1=i+1; v2=i+w[u]; if(j*a[u]>sq && j*a[u]<=m) Add(g[i][m/(j*a[u])], f[v1][j]); else if(j*a[u]<=m) Add(f[i][j*a[u]], f[v1][j]); if(j>=a[u]) Add(g[i][j/a[u]], g[v1][j]); 
//			
//			
//			Add(f[i][j], f[v2][j]); Add(g[i][j], g[v2][j]); }}for(i=1; i<=sq; ++i) Add(ans, f[1][i]+g[1][i]); //	printf("# %lld : %lld\n", x, ans); dfs(x, 0); p[x]=1; for(int y : G[x]) if(!p[y]) {dfs(y, x); sum=w[y]; mx[rt=0]=1e9; dfs(y, x); dfz(rt); }
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);freopen("fn.in", "r", stdin);freopen("fn.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); m=read(); sq=sqrt(m); 
//	printf("# %lld\n", sq); for(i=1; i<=n; ++i) a[i]=read(); for(i=1; i<n; ++i) {u=read(); v=read(); G[u].pb(v); G[v].pb(u); }sum=n; mx[rt=0]=1e9; dfs(1, 0); Rt=rt; 
//	printf("%lld\n", rt); dfz(rt);printf("%lld", (ans%mo+mo)%mo); return 0;
}

这篇关于点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp:0922T4的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/283110

相关文章

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

linux解压缩 xxx.jar文件进行内部操作过程

《linux解压缩xxx.jar文件进行内部操作过程》:本文主要介绍linux解压缩xxx.jar文件进行内部操作,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、解压文件二、压缩文件总结一、解压文件1、把 xxx.jar 文件放在服务器上,并进入当前目录#

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

使用Python进行GRPC和Dubbo协议的高级测试

《使用Python进行GRPC和Dubbo协议的高级测试》GRPC(GoogleRemoteProcedureCall)是一种高性能、开源的远程过程调用(RPC)框架,Dubbo是一种高性能的分布式服... 目录01 GRPC测试安装gRPC编写.proto文件实现服务02 Dubbo测试1. 安装Dubb

Linux使用scp进行远程目录文件复制的详细步骤和示例

《Linux使用scp进行远程目录文件复制的详细步骤和示例》在Linux系统中,scp(安全复制协议)是一个使用SSH(安全外壳协议)进行文件和目录安全传输的命令,它允许在远程主机之间复制文件和目录,... 目录1. 什么是scp?2. 语法3. 示例示例 1: 复制本地目录到远程主机示例 2: 复制远程主

windows系统上如何进行maven安装和配置方式

《windows系统上如何进行maven安装和配置方式》:本文主要介绍windows系统上如何进行maven安装和配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. Maven 简介2. maven的下载与安装2.1 下载 Maven2.2 Maven安装2.

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y

Go语言中使用JWT进行身份验证的几种方式

《Go语言中使用JWT进行身份验证的几种方式》本文主要介绍了Go语言中使用JWT进行身份验证的几种方式,包括dgrijalva/jwt-go、golang-jwt/jwt、lestrrat-go/jw... 目录简介1. github.com/dgrijalva/jwt-go安装:使用示例:解释:2. gi

SpringBoot如何对密码等敏感信息进行脱敏处理

《SpringBoot如何对密码等敏感信息进行脱敏处理》这篇文章主要为大家详细介绍了SpringBoot对密码等敏感信息进行脱敏处理的几个常用方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录​1. 配置文件敏感信息脱敏​​2. 日志脱敏​​3. API响应脱敏​​4. 其他注意事项​​总结