AtCoder Beginner Contest 336 G. 16 Integers(图计数 欧拉路径转欧拉回路 矩阵树定理 best定理)

题目

给16个非负整数,x[i∈(0,1)][j∈(0,1)][k∈(0,1)][l∈(0,1)]

求长为n+3的01串的方案数,满足长度为4的ijkl(2*2*2*2,16种情况)串恰为x[i][j][k][l]个

答案对998244353取模

思路来源

https://www.cnblogs.com/tzcwk/p/matrix-tree-best-theroem.html

矩阵树定理 - OI Wiki

知识点总结

矩阵树定理

对于一张无向图G,

记D为其度数矩阵,满足:

1. D[i][i]=i的度数

2. D[i][j]=0(i≠j)

记A为其邻接矩阵,满足:

1. A[i][j]=i与j之间边的条数,如果有重边则算作多条边。

记基尔霍夫矩阵(拉普拉斯矩阵)K=D−A,

则去掉第k行第k列得到的矩阵行列式即为G生成树的个数。

BEST 定理

对于一个欧拉图(有向图)而言,

从x出发回到x的欧拉回路的个数为:

t^{root}(n,k)*\prod_{v\epsilon V}(deg(v)-1)!

其中,t^{root}(n,k)为任一个点的根向树形图的数量,用矩阵树定理求得,

后半部分,即对于每个点,再乘以每个点的度数减1的阶乘

根向树形图

根向树形图是一棵树,所有边都往根的方向指

一些技巧

求欧拉路径的数量

二层枚举欧拉路径的起点、终点,钦定加一条终点到起点的边,转化为求欧拉回路

仅要求所有边经过一次(部分点可以孤立)

忽略掉孤立点后,对剩下的点离散化后,重新建矩阵,求矩阵的秩

需要视题目决定是否需要乘deg[v](从v出发回到v)

少乘度数的是带循环同构的边序列

思路来源

官方题解

题解

1. 把形如abcd的出现次数,转化为abc->bcd有向边的边的条数,

转化为成边数后,即求欧拉路径条数,

枚举欧拉路径起点终点后,强制加一条边,转成欧拉回路后,套用best定理

2. 对于枚举起点为i,终点为j的情况,先强制加一条j->i的边,

统计每个点x的入度in[x]、出度out[x]

① 忽略孤立点,即in[x]=out[x]=0

② 若in[x]和out[x]不相等,则无解

③ 若x非孤立点,且与i不联通,则无解

否则,

④忽略孤立点,将非孤立点重新编号建边

⑤按定义构建基尔霍夫矩阵K=D-A

即a[k][k]+=in[k](D矩阵),a[k][l]-=b[k][l](A矩阵)

            rep(k,0,7){ // 基尔霍夫矩阵a[to[k]][to[k]]=in[k];rep(l,0,7){if(!to[l])continue;a[to[k]][to[l]]-=b[k][l];//printf("%d ",a[k][l]);}}

⑥求矩阵的秩,得到生成树数量,依次乘以(deg[i]-1)!得到欧拉回路数量

⑦欧拉回路是一个环,每个环被统计一次,

固定新增的那条边在串最后指向串最前,即可唯一对应一个串

但是注意到,当abc->bcd有两条相同的边x1、x2时,二者的顺序会被欧拉回路视为不同的方案

而在序列中,abcd是一个唯一的序列,被重复计算

所以,需要除掉完全相同的边的顺序,类似可重集全排列的方案数

代码

// Problem: G - 16 Integers
// Contest: AtCoder - AtCoder Beginner Contest 336
// URL: https://atcoder.jp/contests/abc336/tasks/abc336_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10,M=16,K=8,mod=998244353;
int t,fac[N],x[M],b[K][K],in[K],out[K],par[K];
int find(int x){return par[x]==x?x:par[x]=find(par[x]);
}
void merge(int x,int y){x=find(x),y=find(y);if(x==y)return;par[y]=x;
}
int modpow(int x,int n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
// 求解行列式时模数不是质数,没法求逆元,这时只能利用辗转消除法进行高斯消元
// 矩阵的秩
int Gauss(vector<vector<int> >&a,int n){//printf("x:%d\n",x);int ans=1;//swap(a[0],a[x]);for(int i=2;i<=n;i++){for(int j=i;j<=n;j++){if(!a[i][i] && a[j][i]){swap(a[i],a[j]);ans=mod-ans;break;}}ans=1ll*ans*a[i][i]%mod;for(int j=1;j<=n;j++){if(i==j || !a[j][i])continue;int t=1ll*a[j][i]*modpow(a[i][i],mod-2,mod)%mod;for(int k=1;k<=n;k++){a[j][k]=(a[j][k]-1ll*t*a[i][k]%mod+mod)%mod;}}}return ans;
}
void sol(){rep(i,0,15){b[i>>1][i&7]=x[i];}int res=0;rep(i,0,7){rep(j,0,7){b[j][i]++;//欧拉路径->欧拉回路bool ok=1;memset(in,0,sizeof in);memset(out,0,sizeof out);rep(k,0,7)par[k]=k;rep(k,0,7){rep(l,0,7){in[l]+=b[k][l];out[k]+=b[k][l];if(b[k][l])merge(k,l);//if(b[k][l])printf("i:%d j:%d k:%d l:%d b:%d\n",i,j,k,l,b[k][l]);}}rep(k,0,7){if(!in[k] && !out[k])continue;//孤立点,只是要求遍历所有边时,可忽略if(in[k]!=out[k])ok=0;//判出入度if(find(k)!=find(i))ok=0;//判连通//printf("i:%d j:%d k:%d in:%d out:%d\n",i,j,k,in[k],out[k]);}if(!ok){b[j][i]--;continue;}int bs=1;//deg[i]rep(k,0,7){if(!in[k])continue;bs=1ll*bs*fac[in[k]-1]%mod;//\prod (deg[i]-1)}vector<vector<int>>a(K+1,vector<int>(K+1,0));vector<int>to(K+1,0);int id=0;rep(k,0,7){if(in[k])to[k]=++id;}rep(k,0,7){ // 基尔霍夫矩阵a[to[k]][to[k]]=in[k];rep(l,0,7){if(!to[l])continue;a[to[k]][to[l]]-=b[k][l];//printf("%d ",a[k][l]);}}int rank=Gauss(a,id);//求基尔霍夫矩阵的秩//printf("i:%d j:%d bs:%d rk:%d\n",i,j,bs,rank);bs=1ll*bs*rank%mod;rep(k,0,15){bs=1ll*bs*modpow(fac[x[k]],mod-2,mod)%mod;//去重}res=(res+bs)%mod;b[j][i]--;}}printf("%d\n",res);
}
void init(){fac[0]=1;rep(i,1,N-1)fac[i]=1ll*fac[i-1]*i%mod;
}
int main(){init();rep(i,0,15)sci(x[i]);sol();return 0;
}

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

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

相关文章

深度系统QT 环境搭建

1.QT安装 不折腾最新版直接去商店搜索QT安装。 2.修改su密码&#xff0c;安装需要权限 打开一个终端&#xff0c;然后输入下面的命令&#xff1a;按照提示输入密码按回车就行。 sudo passwd 回车后会出现让你输入现在这个账户的密码&#xff1a; 3.编译环境安装。 安…

生活自来水厂污水处理设备需要哪些

生活自来水厂是确保我们日常用水质量安全的重要设施。在自来水的生产过程中&#xff0c;污水处理设备是不可或缺的环节。那么&#xff0c;生活自来水厂的污水处理设备都有哪些呢&#xff1f;本文将为您详细介绍。 首先&#xff0c;生活自来水厂的污水处理设备主要包括预处理设备…

大语言模型系列-总述

大语言模型发展史 研究人员发现&#xff0c;扩展预训练模型&#xff08;Pre-training Language Model&#xff0c;PLM&#xff09;&#xff0c;例如扩展模型大小或数据大小&#xff0c;通常会提高下游任务的模型性能&#xff0c;模型大小从几十亿&#xff08;1 B 10亿&#x…

Linux常用命令大全(三)

系统权限 用户组 1. 创建组groupadd 组名 2. 删除组groupdel 组名 3. 查找系统中的组cat /etc/group | grep -n “组名”说明&#xff1a;系统每个组信息都会被存放在/etc/group的文件中1. 创建用户useradd -g 组名 用户名 2. 设置密码passwd 用户名 3. 查找系统账户说明&am…

MySQL的多表数据记录查询笔记

关系数据操作 合并查询数据记录 在MySQL中通过关键字UNION来实现并操作&#xff0c;即可以通过其将多个SELECT语句的查询结果合并在一起组成新的关系。 两张表&#xff0c;表1 和表2 带有关键字UNION的合并操作 关键字UNION会把查询结果集直接合并在一起&#xff0c;同时将…

力扣每日一题--2088. 统计农场中肥沃金字塔的数目

看到这道题有些人很容易放弃&#xff0c;其实这道题不是很难&#xff0c;主要是题目长&#xff0c;读的容易让人放弃&#xff0c;但是 只要抓住一些性质就可以解决该问题。 本题中的定义放到图像里其实就是个金字塔&#xff0c;下层的那部分比上一层的那部分&#xff0c;长度加…

What does `ResponseEntity` do?

ResponseEntity 作为 Spring MVC controller层 的 HTTP response&#xff0c;包含 status code, headers, body 这三部分。 正常场景 RestController Slf4j public class SearchController {AutowiredUserService userService;RequestMapping(value "/getAllStudents4&…

Androidmanifest文件加固和对抗

前言 恶意软件为了不让我们很容易反编译一个apk&#xff0c;会对androidmanifest文件进行魔改加固&#xff0c;本文探索androidmanifest加固的常见手法以及对抗方法。这里提供一个恶意样本的androidmanifest.xml文件&#xff0c;我们学完之后可以动手实践。 1、Androidmanife…

文心一言 vs. ChatGPT:哪个更胜一筹?

文心一言 vs. ChatGPT&#xff1a;从简洁美到深度思考的文本生成之旅 近年来&#xff0c;文本生成工具的崛起使得人们在表达和沟通方面拥有了更多的选择。在这个领域中&#xff0c;文心一言和ChatGPT作为两个备受瞩目的工具&#xff0c;各自以独特的优势展现在用户面前。本文将…

国际版WPS Office 18.6.1

【应用名称】&#xff1a;WPS Office 【适用平台】&#xff1a;#Android 【软件标签】&#xff1a;#WPS 【应用版本】&#xff1a;18.6.1 【应用大小】&#xff1a;160MB 【软件说明】&#xff1a;软件日常更新。WPS Office是使用人数最多的移动办公软件。独有手机阅读模式…

从零开始的神经网络

了解如何在没有框架帮助的情况下构建神经网络的基础知识&#xff0c;这些框架可能使其更易于使用 在 Python 中创建具有不同架构的复杂神经网络应该是任何机器学习工程师或数据科学家的标准做法。但是&#xff0c;真正了解神经网络的工作原理同样有价值。在本文中&#xff0c;…

代码随想录刷题笔记(DAY11)

今日总结&#xff1a;继续准备期末&#xff0c;今天的算法题目比较简单&#xff0c;晚上看看能不能再整理一篇前端的笔记。 Day 11 01. 有效的括号&#xff08;No. 20&#xff09; 题目链接 代码随想录题解 1.1 题目 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff…

【C++】__declspec含义

目录 一、__declspec(dllexport)如果这篇文章对你有所帮助&#xff0c;渴望获得你的一个点赞&#xff01; 一、__declspec(dllexport) __declspec(dllexport) 是 Microsoft Visual C 编译器提供的一个扩展&#xff0c;用于指示一个函数或变量在 DLL&#xff08;动态链接库&…

非常好用的个人工作学习记事本Obsidian

现在记事本有两大流派&#xff1a;Obsidian 和Notion&#xff0c;同时据说logseq也很不错 由于在FreeBSD下后两种都没有相关ports&#xff0c;所以优先尝试使用Obsidian Obsidian简介 Obsidian是基于Markdown文件的本地知识管理软件&#xff0c;并且开发者承诺Obsidian对于个…

2024年腾讯云服务器配置价格表(机型/磁盘/宽带/CPU)

腾讯云服务器租用价格表&#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元一年…

Swoft - Bean

一、Bean 在 Swoft 中&#xff0c;一个 Bean 就是一个类的一个对象实例。 它(Bean)是通过容器来存放和管理整个生命周期的。 最直观的感受就是省去了频繁new的过程&#xff0c;节省了资源的开销。 二、Bean的使用 1、创建Bean 在【gateway/app/Http/Controller】下新建一个名为…

Vue + JS + tauri 开发一个简单的PC端桌面应用程序

Vue JS tauri 开发一个简单的PC端桌面应用程序 文章目录 Vue JS tauri 开发一个简单的PC端桌面应用程序1. 环境准备1.1 安装 Microsoft Visual Studio C 生成工具[^2]1.2 安装 Rust[^3] 2. 使用 vite 打包工具创建一个 vue 应用2.1 使用Vite创建前端Vue项目2.2 更改Vite打包…

jmeter--常用插件及服务器监控(14)

一.jmeter插件管理器 下载jmeter插件管理器&#xff1a;plugins-manager.jar 下载plugins-manager.jar并将其放入lib/ext目录&#xff0c;然后重启JMeter。 插件管理界面 打开选项->Plugins Manager&#xff08;界面见下图&#xff09;&#xff0c;“Installed Plugns”…

牛客周赛 Round 3 解题报告 | 珂学家 | 贪心思维场

前言 寒之不寒无水也&#xff0c;热之不热无火也。 整体评价 感觉比较简单&#xff0c;更加侧重于思维吧。和前几场的Round系列&#xff0c;风格不太一样。 A. 游游的7的倍数 因为连续7个数&#xff0c;比如有一个数是7的倍数 因此从个位数中着手添加&#xff0c;是最好的选…

了解Dubbo配置:优先级、重试和容错机制的秘密【五】

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 了解Dubbo配置&#xff1a;优先级、重试和容错机制的秘密【五】 前言Dubbo高级配置概述不同配置覆盖关系重试与容错处理机制负载均衡机制 前言 Dubbo作为一款强大的分布式服务框架&#xff0c;其高级…