球球的排列
题目传送门
引
计数DP,好像特别经典,有两种做法,我只会 O ( n 3 ) O(n^3) O(n3),有 O ( n 2 ) O(n^2) O(n2)的
解法
首先, 若 x y = p 2 且 x z = q 2 , 则 y z = ( p q x ) 2 若xy=p^2且xz=q^2,则yz=(\frac{pq}{x} )^2 若xy=p2且xz=q2,则yz=(xpq)2 所以题目中给出的关系具有传递性,故先预处理,不可相邻的球分在一个组
为了方便,下面叫同一组的球为同色
伪代码如下:
bool check(ll x){ll tmp=sqrt(x);return (tmp*tmp==x);
}for(int i=1;i<=n;i++) {a[i]=read(),b[i]=i;for(int j=1;j<i;j++) {if(check(1ll*a[i]*a[j])) {b[i]=j;break;}}
}
接下来,
设计状态
首先我们无脑枚举一维 i i i表示前 i i i个球,注意同色的球排序后的序列是连续的
观察题目的限制相当于同色的球不能相邻,设计后两维要考虑好同色和相邻
f i , j , . k : 前 i 个球,共有 j + k 对相邻的球同色,其中 j 对跟第 i 个球异色, k 对同色 f_{i,j,.k}:前i个球,共有j+k对相邻的球同色,其中j对跟第i个球异色,k对同色 fi,j,.k:前i个球,共有j+k对相邻的球同色,其中j对跟第i个球异色,k对同色
那么最后的答案 a n s = f n , 0 , 0 ans=f_{n,0,0} ans=fn,0,0
设计出了状态其实就成功了一半,但这道题的转移也很毒瘤,客官且看
状态转移
考虑 f i f_i fi与 f i − 1 f_{i-1} fi−1的关系, f i f_i fi的状态都是由 i − 1 i-1 i−1个球的 i i i个空隙插入一个球而来的
那么第 i i i个球与第 i − 1 i-1 i−1个球有两种关系:a.同色;b.异色
第 i i i个球插入的位置也有两种可能:c.插入两个同色球之间;d.插入两个异色球之间
所以对6种可能分别考虑转移:
1. a与c
发现,此时前 i − 1 i-1 i−1个球已有与 i i i同色的,那么明显第 i i i个球放在与其同色的球旁边转移不同,设排列中已有 c n t cnt cnt个球与 i i i同色,此时有:
f i , j , k = f i − 1 , j , k − 1 ∗ ( c n t ∗ 2 − ( k − 1 ) ) f_{i,j,k}=f_{i-1,j,k-1}*(cnt*2-(k-1)) fi,j,k=fi−1,j,k−1∗(cnt∗2−(k−1))
然后第 i i i个球插入的位置是与自己异色的球间,让 j j j减少了1,此时有:
f i , j , k = f i − 1 , j + 1 , k ∗ ( j + 1 ) f_{i,j,k}=f_{i-1,j+1,k}*(j+1) fi,j,k=fi−1,j+1,k∗(j+1)
2.a与d
减去前两种情况,还剩 i − c n t ∗ 2 + k − j i-cnt*2+k-j i−cnt∗2+k−j种情况, j , k j,k j,k不变,此时有:
f i , j , k = f i − 1 , j , k ∗ ( i − c n t ∗ 2 + k − j ) f_{i,j,k}=f_{i-1,j,k}*(i-cnt*2+k-j) fi,j,k=fi−1,j,k∗(i−cnt∗2+k−j)
3.b与c
可知第 i i i个球的颜色是首次出现,故 k k k=0,让 ( j + k ) (j+k) (j+k)减少了1,所以要枚举 j ‘ j‘ j‘和 k ’ k’ k’,有:
f i , j , 0 = ∑ j ′ + k ′ = j + 1 f i , j ′ , k ′ ∗ ( j + 1 ) f_{i,j,0}=\sum_{j'+k'=j+1} f_{i,j',k'} *(j+1) fi,j,0=j′+k′=j+1∑fi,j′,k′∗(j+1)
4.b与d
对 j , k j,k j,k不产生影响,枚举即可,此时有:
f i , j , 0 = ∑ j ′ + k ′ = j f i , j ′ , k ′ ∗ ( i − j ) f_{i,j,0}=\sum_{j'+k'=j} f_{i,j',k'}*(i-j) fi,j,0=j′+k′=j∑fi,j′,k′∗(i−j)
代码实现倒是简单,放一下
code:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 3e2 + 5,mod=1e9+7;
int n,cnt;
int f[2][N][N],a[N],b[N];
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*10+ch-'0',ch=getchar();return x*f;
}
bool check(ll x){ll tmp=sqrt(x);return (tmp*tmp==x);
}
int main() {n=read();for(int i=1;i<=n;i++) {a[i]=read(),b[i]=i;for(int j=1;j<i;j++) {if(check(1ll*a[i]*a[j])) {b[i]=j;break;}}}sort(b+1,b+1+n);f[0][0][0]=1;for(int i=1;i<=n;i++,cnt++) {int now=i&1,pre=now^1;memset(f[now],0,sizeof f[now]);if(b[i]==b[i-1]){for(int j=0;j<i;j++) {for(int k=0;k<=cnt;k++){if(k) f[now][j][k]=(1ll*f[now][j][k]+1ll*f[pre][j][k-1]*(cnt*2-(k-1)))%mod;f[now][j][k]=(1ll*f[now][j][k]+1ll*f[pre][j+1][k]*(j+1))%mod;f[now][j][k]=(1ll*f[now][j][k]+1ll*f[pre][j][k]*(i-cnt*2+k-j))%mod;}}}else {cnt=0;for(int j=0;j<i;j++){for(int k=0;k<=j+1;k++){if(k<=j) f[now][j][0]=(1ll*f[now][j][0]+1ll*f[pre][k][j-k]*(i-j))%mod;f[now][j][0]=(1ll*f[now][j][0]+1ll*f[pre][k][(j+1)-k]*(j+1))%mod;}}}}printf("%d\n",f[n&1][0][0]);
}
TXL
相关文章:
球球的排列
题目传送门 引 计数DP,好像特别经典,有两种做法,我只会 O ( n 3 ) O(n^3) O(n3),有 O ( n 2 ) O(n^2) O(n2)的 解法 首先, 若 x y p 2 且 x z q 2 , 则 y z ( p q x ) 2 若xyp^2且xzq^2,则yz(\frac{pq}{x} )^2 若xyp2且xzq2,则yz(xpq…...
1783_CMD启动MATLAB同时执行一个脚本
全部学习汇总: GitHub - GreyZhang/g_matlab: MATLAB once used to be my daily tool. After many years when I go back and read my old learning notes I felt maybe I still need it in the future. So, start this repo to keep some of my old learning notes…...
C语言中内存分配的几种方式
目录 C语言中内存分配的几种方式静态内存分配栈内存分配堆内存分配内存映射文件 C语言中内存分配的几种方式 静态内存分配 静态内存分配是在程序编译时分配内存,通常用于全局变量和静态变量。这些变量的内存空间在程序的整个运行期间都是存在的。 栈内存分配 栈内存…...
组相联cache如何快速实现cache line eviction并使用PMU events验证
如何快速实现cache line eviction 一,什么是cache hit、miss、linefill、evict ?1.1 如果要程序员分别制造出cache hit、miss、linefill、evict这四种场景,该怎么做? 二,实现cache line eviction的方法1.1 直接填充法3…...
【Stable Diffusion安装】支持python3.11 window版
前言 主要的安装步骤是参考B站播放量第一的视频,但是那位阿婆主应该是没有编程经验,只强调使用3.10,而python最新版本是3.11。 理论上来说,只是一个小版本的不同,应该是可以安装成功了。自己摸索了下,挺费…...
Anycloud37D平台移植wirelesstools
0. 环境准备 下载 :https://www.linuxfromscratch.org/blfs/view/svn/basicnet/wireless_tools.html 1. 交叉编译wireless_tools tar xzf wireless_tools.29.tar.gz cd wireless_tools.29/打开Makefile,修改配置: ## Compiler to use (mo…...
海康机器人工业相机 Win10+Qt+Cmake 开发环境搭建
文章目录 一. Qt搭建海康机器人工业相机开发环境 一. Qt搭建海康机器人工业相机开发环境 参考这个链接安装好MVS客户端 Qt新建一个c项目 cmakeList中添加海康机器人的库,如下: cmake_minimum_required(VERSION 3.5)project(HIKRobotCameraTest LANG…...
使用MDK5的一些偏僻使用方法和谋个功能的作用
程序下载后无法运行 需要勾选如下库,是优化后的库; MicroLib和标准C库之间的主要区别是: 1、MicroLib是专为深度嵌入式应用程序而设计的。 2、MicroLib经过优化,比使用ARM标准库使用更少的代码和数据内存。 3、MicroLib被设计成在没有操作…...
【实战】十一、看板页面及任务组页面开发(六) —— React17+React Hook+TS4 最佳实践,仿 Jira 企业级项目(二十八)
文章目录 一、项目起航:项目初始化与配置二、React 与 Hook 应用:实现项目列表三、TS 应用:JS神助攻 - 强类型四、JWT、用户认证与异步请求五、CSS 其实很简单 - 用 CSS-in-JS 添加样式六、用户体验优化 - 加载中和错误状态处理七、Hook&…...
在 Amazon 搭建无代码可视化的数据分析和建模平台
现代企业常常会有利用数据分析和机器学习帮助解决业务痛点的需求。如制造业中,利用设备采集上来的数据做预测性维护,质量控制;在零售业中,利用客户端端采集的数据做渠道转化率分析,个性化推荐等。 亚马逊云科技开发者…...
Pinely Round 2 (Div. 1 + Div. 2) G. Swaps(组合计数)
题目 给定一个长度为n(n<1e6)的序列,第i个数ai(1<ai<n), 操作:你可以将当前i位置的数和a[i]位置的数交换 交换可以操作任意次,求所有本质不同的数组的数量,答案对1e97取模 思路来源 力扣群 潼神 心得 感…...
elasticSearch+kibana+logstash+filebeat集群改成https认证
文章目录 一、生成相关证书二、配置elasticSearh三、配置kibana四、配置logstash五、配置filebeat六、连接https es的java api 一、生成相关证书 ps:主节点操作 切换用户:su es 进入目录:cd /home/es/elasticsearch-7.6.2 创建文件&#x…...
GPT带我学-设计模式-迭代器模式
1 什么是迭代器设计模式? 迭代器设计模式是一种行为型设计模式,用于提供一种统一的方式来遍历一个集合对象中的元素,而不需要暴露该对象的内部结构。它将集合对象的遍历操作与集合对象本身分离开来,使得遍历操作可以独立于集合对…...
数学建模--层次分析法(AHP)的Python实现
目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 """ AHP:层次分析法,层次分析法还是比较偏向于主观的判断的,所以在建模的时候尽可能不要去使用层次分析法 不过在某些创新的评价方法上,也是能够运用层次分析使得评价变得全面一些,有可…...
机器学习笔记之最优化理论与方法(三)凸集的简单认识(下)
机器学习笔记之最优化理论与方法——凸集的简单认识[下] 引言回顾:基本定义——凸集关于保持集合凸性的运算仿射变换 凸集基本性质:投影定理点与凸集的分离支撑超平面定理 引言 继续凸集的简单认识(上)进行介绍,本节将介绍凸集的基本性质以及…...
Apipost:API文档、调试、Mock与测试的一体化协作平台
随着数字化转型的加速,API(应用程序接口)已经成为企业间沟通和数据交换的关键。而在API开发和管理过程中,API文档、调试、Mock和测试的协作显得尤为重要。Apipost正是这样一款一体化协作平台,旨在解决这些问题…...
Homebrew下载安装及使用教程
Homebrew是什么? 简单来说,就是用命令行的形式去管理mac系统的包或软件。 安装命令 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"国内请使用镜像源进行下载 执行上述命令后会要求输入…...
【Codeforces】CF193D Two Segments
题目链接 CF方向 Luogu方向 题目解法 考虑在值域上的问题:有多少段区间,对应在排列上不超过 2 2 2 段 肯定需要枚举一个端点,另一个快速算出,考虑枚举值域区间右端点 r r r,计算 l l l 可以发现,新增…...
内存管理概述
前言 在学习计算机科学时,内存管理是一个非常重要的概念。简单地说,内存是计算机用来存储和访问数据的地方。而内存管理是计算机系统如何分配、使用和管理内存的过程。 为什么要学习内存管理? 1. 高效性:内存管理能够帮助计算机更…...
Spring的重试机制-SpringRetry
在我们的日常开发中,经查会遇到调用接口失败的情况,这时候就需要通过一些方法来进行重试,比如通过while循环手动重复调用或,或者通过记录错误接口url和参数到数据库,然后手动调用接口,或者通过JDK/CGLib动态…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
