首页 > 其他分享 >[ZR] 城市

[ZR] 城市

时间:2024-11-08 18:29:53浏览次数:1  
标签:13 颜色 导出 bmod 子图 sum 城市 ZR

source:zr 二十联测 day 15 C

题意

给定 \(n\) 个点 \(m\) 条边的图,求该图导出连通子图数量对 2 取模的结果。保证一条边两个端点编号差 \(\le 13\)。

\(n\le 50\)。

分析

原题相当于求连通块数量为 1 的导出子图的数量。

考虑利用模数为 2 的性质。

性质:答案等于 \(\dfrac{\sum 2^{f(S)}\bmod 4}{2}\),其中 \(f(S)\) 表示导出子图 \(S\) 的连通块数量。

\(2^{f(S)}\bmod 4\) 的值仅在 \(f(S)=1\) 的情况下为 \(2\),其他情况下都为 \(0\)。故 \(\sum 2^{f(S)}\bmod 4=2\sum[f(S)=1]\),而 \(\sum[f(S)=1]\) 就是答案。

题目转化为求 \(\sum 2^{f(S)}\bmod 4\) 的值。

为 \(2^{f(S)}\) 寻找一个组合意义,相当于,对该导出子图染上黑白两种颜色的方案数。转化一下,就是给每个点染黑白两色,使得有边相连的两个点颜色相同。

同理,为 \(\sum 2^{f(S)}\) 寻找一个组合意义,相当于,对整个图染上黑白两种颜色或者不染色(不染色表示不在子图中),使得有边相连的两个点颜色相同。

据此可以直接设计 \(f_{i,S}\) 表示已经填了 \(1\sim i\) 的点,后 \(13\) 个点的染色情况是 \(S\)。转移考虑 \(i\) 填什么颜色即可,合法性判断可以 \(O(1)\) 做到。于是时间复杂度 \(O(n3^{13})\)。

标签:13,颜色,导出,bmod,子图,sum,城市,ZR
From: https://www.cnblogs.com/dcytrl/p/18535556

相关文章

  • [ZR] WI
    source:zr二十联测day16B题意给定\(n\)个数\(a_i\)。每次你需要花费\(c\)在剩余的数中均匀随机获得一个数,你可以选择留下这个数,此时游戏结束且得分为该数值;否则将这个数扔掉(但不放回),然后游戏继续。求最大期望。要求时间复杂度\(O(n)\)。分析将\(a_i\)降序排序。......
  • mapreduce案例_用户停留时间关联城市名
    importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.Path;importorg.apache.hadoop.io.LongWritable;importorg.apache.hadoop.io.Text;importorg.apache.hadoop.mapreduce.lib.input.FileSplit;importorg.apache.hadoop.mapreduce.Job;impo......
  • SpringBoot图书馆借阅管理系统49zr9 本系统(程序+源码+数据库+调试部署+开发环境)带论文
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表系统内容:读者,图书分类,图书信息,图书借阅,图书归还,图书主题,出版时间,出版社分布,图书统计开题报告内容一、研究背景与意义随着信息技术的快速发展,图书馆作......
  • 基于Java+SpringBoot+Vue+HTML5城市垃圾分类管理系统(源码+LW+调试文档+讲解等)/城市
    博主介绍......
  • springboot+vue城市闪送微信小程序【开题+程序+论文】
    系统程序文件列表开题报告内容研究背景随着城市化进程的加速,人们对生活便捷性的需求日益增强,特别是在快递配送领域。传统的快递服务虽然覆盖面广,但在即时配送方面往往存在响应慢、成本高的问题。近年来,以“闪送”为代表的即时配送服务迅速崛起,以其高效、灵活的特点满足了城......
  • java计算机毕业设计城市垃圾分类回收管理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容城市垃圾分类回收管理系统的相关研究一、研究背景随着城市化进程的迅猛发展,城市垃圾产量呈现出急剧增长的态势。传统的垃圾处理模式,如简易堆放或填埋,已经暴......
  • 数字孪生技术:未来城市的智能镜像!
    内容概要在科技迅猛发展的今天,数字孪生技术犹如城市的“数字双胞胎”,为我们描绘出未来城市的美好蓝图。想象一下,现实中的万象都能在虚拟的世界中以1:1的比例呈现,连你早上的咖啡喝到第几口、街边小狗们的聚会都毫无遗漏!这项技术不仅让管理者能实时获取城市运行的数据,还像个神奇......
  • java计算机毕业设计城市养老服务预约系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着社会的快速发展,人口老龄化现象日益严重,城市养老服务面临巨大挑战。传统的养老服务方式在服务预约、信息管理等方面存在诸多不便,难以满足老年......
  • 基于Spring Boot的城市公交在线查询系统
    目录前言 一、技术栈二、系统功能介绍三、核心代码1、登录模块 2、文件上传模块3、代码封装前言随着世界经济信息化、全球化的到来和互联网的飞速发展,推动了各行业的改革。若想达到安全,快捷的目的,就需要拥有信息化的组织和管理模式,建立一套合理、动态的、交互友......
  • three.js+vue3三维地图下钻地图,实现下钻全国-》省份-》城市-》区县
    案例效果截图:具体场景和功能,详见b站视频:https://www.bilibili.com/video/BV1Kb421q7c4/?vd_source=7d4ec9c9275b9c7d16afe9b4625f636c 案例逻辑代码:<template><divid="chinaMap"><divid="threejs"ref="threejs"></div>......