当前位置: 首页 > news >正文

扩域技术

核心思想是将无法处理的运算参量单独设为一个未知量,也就是变成维护二元组,多个未知量就是多元组,然后设置它们的合并规则进行计算。

一般而言,最终的未知量都会消去。

例如 NOI2025 集合 中,我们需要涉及到处理含 \(0\) 算式的乘除法,可以将数字表达为 \(x·0^y\) 的形式,用二元组 \((x,y)\) 来维护。

不过显而易见的只支持乘除法以及 \(y=0\) 的加减法,但这足以。

另一个例子是斐波那契数列,\(f_n=\frac{(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n}{\sqrt 5}\)

常见的算法是用矩阵乘法,但更快的做法是:

  1. 若存在 \(x^2\equiv 5 (\bmod p)\) 则可以直接带入 \(x\) 进行计算。
  2. 设变量 \(t=\sqrt 5\),将数字 \(x+y\sqrt 5\) 记作 \((x,y)\),重定义运算:
    • \((a,b)+(c,d)=(a+c,b+d)\)
    • \((a,b)\times (c,d)=(ac+t^2bd,ad+bc)\)

由于是 \(\sqrt 5\) 的形式,\(t^2=5\),因此事实上是维护的一个关于 \(t\) 的一次多项式的运算

其他类似的也可以这样做,或者说可以直接将其当做一个正常的数字来运算,例如 P5320 之中的 \(\sqrt 3\)

扩展一下,若式子中同时含有 \(\sqrt 3,\sqrt 5\),可以设计变量 \(a=\sqrt 3,b=\sqrt 5,c=\sqrt 15\) 维护四元组。

若含有 \(3^{\frac{1}{3}}\) 之类的数字,可以设计 \(a=3^{\frac{1}{3}},b=3^{\frac{2}{3}}\) 来进行运算。

事实上都是含变量的多项式运算,只不过定义了新的四则运算规则。

http://www.jsqmd.com/news/154263/

相关文章:

  • 2025卫生间瓷砖品牌TOP5权威推荐:深度测评指南 - 工业推荐榜
  • YOLOv10来了!新架构带来的算力需求变化分析
  • 阀门生产厂、品牌供应商与服务商家的优质之选——天津中阀科技 - 工业推荐榜
  • YOLO模型太大无法部署?教你用GPU+TensorRT极致压缩
  • (39)AOP的实际案例
  • 2025年郑州美业培训学校排行榜,新测评精选美业教育机构推荐 - 工业品牌热点
  • (41)事务属性(建议在数据库深入学习)
  • YOLO目标检测模型训练太慢?试试我们的高性能GPU套餐
  • YOLO训练成本太高?我们送你免费GPU token体验包
  • (42)事务的两种开发模式
  • 生成式AI移动应用测试工程方法论
  • 2025白刚玉定制口碑前十强,你选对了吗?磨料/金刚砂/碳化硅/白刚玉/不锈钢灰/精密铸造砂/棕刚玉/铬刚玉/黑碳化硅白刚玉厂家有哪些 - 品牌推荐师
  • YOLO + Triton推理服务器:构建高并发检测服务
  • 2025年谁主沉浮?顶尖重型货架厂家综合评比,重型板材存放架/重型货架超强承重/重型模具货架/伸缩悬臂货架/重型货架重型货架定制厂家哪家强 - 品牌推荐师
  • Compose笔记(六十四)--LottieAnimation
  • HTTP的简介和原理 - saboyou1
  • 2025.12.28博客
  • 智能 Agent 的概念建模与系统特征分析-从传统程序到自主智能体的范式演进
  • vue 甘特图 vxe-gantt table 可视化依赖线的使用,可视化拖拽创建连接线的用法
  • Cloudflare Wrangler CLI 备忘
  • 论文阅读(十二月第四周)
  • 做不出IT毕设,我是废物吗?
  • YOLO模型支持Logstash日志处理管道
  • YOLO模型训练支持CutOut与HideAndSeek图像遮挡增强
  • 2025年三合一过滤洗涤干燥机厂家排名:哈氏合金/搪瓷设备专业制造商推荐 - mypinpai
  • 从“拔网线“看互联网大厂的安全攻防:黑灰产攻击原理与防御实战
  • Next AI Draw.io 核心实现深度分析
  • HTTP的原理 - saboyou1
  • 2025年优质尼龙拖链品牌排行榜,尼龙拖链与其他材质拖链对比优势在哪? - mypinpai
  • 12/28-正式1级打卡题1(课后)