Matrix Equation(高斯线性异或消元+bitset优化)
题目:
登录—专业IT笔试面试备考平台_牛客网
思路:
我们发现对于矩阵C可以一列一列求。
mod2,当这一行相乘1的个数为奇数时,z(i,j)为1,偶数为0,是异或消元。
对于b[i,j]*c[i,j],b[i,j]可以与a[i,i]异或让他转换到左边,而右边一列全为0。
每一列的解是不能确定元素cn个的2^cn。
异或消元可以用bitset优化。
代码:
#include <iostream>
#include<map>
#include<queue>
#include<unordered_map>
#include<cmath>
#include<bitset>
using namespace std;
#define LL long long
const int N=1e3+100;
double eps=1e-12;
const long long mod=998244353;
std::bitset<210> A[210],a[210],b[210];
int n;
LL quick(LL a,LL b,LL mod){
LL ans=1;
while(b){
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
LL guss()
{ int c=1,r=1;
for(c=1;c<=n;c++)
{ int t=r;
for(int i=r+1;i<=n;i++) if(a[i][c]>a[t][c]) t=i;
if(!a[t][c]) continue;
swap(a[t],a[r]);
for(int i=r+1;i<=n;i++)
if(a[i][c])
a[i]=a[i]^a[r];
r++;
}
return quick(2,n-r+1,mod);
}
int main()
{ cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{ int x;
scanf("%d",&x);
if(x) A[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{ int x;
scanf("%d",&x);
if(x) b[i][j]=1;
}
LL ans=1;
for(int j=1;j<=n;j++)
{
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
a[i][k]=A[i][k];
for(int i=1;i<=n;i++) a[i][n+1]=0;
for(int i=1;i<=n;i++)
a[i][i]=a[i][i]^b[i][j];
ans=ans*guss()%mod;
}
cout<<ans<<endl;
return 0;
}
相关文章:
Matrix Equation(高斯线性异或消元+bitset优化)
题目: 登录—专业IT笔试面试备考平台_牛客网 思路: 我们发现对于矩阵C可以一列一列求。 mod2,当这一行相乘1的个数为奇数时,z(i,j)为1,偶数为0,是异或消元。 对于b[i,j]*c[i,j],b[i,j]可以…...
【一图学技术】2.API测试9种方法图解
9种API测试方法 冒烟测试:冒烟测试是一种快速的表面级测试,用于验证软件的基本功能是否正常工作,以确定是否值得进行更详细的测试。功能测试:功能测试是验证软件是否符合预期功能要求的测试类型。它涉及对每个功能进行测试&#…...
力扣刷题----42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图…...
【论文精读】 | 基于图表示的视频抑郁症识别的两阶段时间建模框架
文章目录 0、Description1、Introduction2、Related work2.1 Relationship between depression and facial behaviours2.2 Video-based automatic depression analysis2.3 Facial graph representation 3、The proposed two-stage approach3.1 Short-term depressive behaviour…...
采集PCM,将base64片段转换为wav音频文件
需求 开始录音——监听录音数据——结束录音 在监听录音数据过程中:客户端每100ms给前端传输一次数据(pcm数据转成base64),前端需要将base64片段解码、合并、添加WAV头、转成File、上传到 OSS之后将 url 给到服务端处理。 {num…...
eclipse ui bug
eclipse ui bug界面缺陷,可能项目过多,特别maven项目过多,下载,自动编译,加载更新界面异常 所有窗口死活Restore不回去了 1)尝试创建项目,还原界面,失败 2)关闭所有窗口&…...
前端获取blob文件格式的两种格式
第一种,后台传递给前台是base64格式的JSON数据 这时候前台拿到base64格式的数据可以通过内置的atob解码方法结合new Uint8Array和new Blob方法转换成blob类型的数据格式,然后可以使用blob数据格式进行操作,虽然base64转换成blob要经过很多步骤,但幸运的是这些步骤都是固定的,因…...
向日葵RCE复现(CNVD-2022-10270/CNVD-2022-03672)
一、环境 1.1 网上下载低版本的向日葵<2022 二、开始复现 2.1 在目标主机上打开旧版向日葵 2.2 首先打开nmap扫描向日葵主机端口 2.3 在浏览器中访问ip端口号cgi-bin/rpc?actionverify-haras (端口号:每一个都尝试,直到获取到session值…...
Postman中的负载均衡测试:确保API的高可用性
Postman中的负载均衡测试:确保API的高可用性 在微服务架构和分布式系统中,API的负载均衡是确保系统高可用性和可扩展性的关键技术之一。Postman作为一个多功能的API开发和测试平台,提供了多种工具来帮助测试人员模拟高负载情况下的API表现。…...
anaconda+tensorflow+keras+jupyter notebook搭建过程(CPU版)
AnacondaTensorFlowKeras 环境搭建教程...
LitCTF2024赛后web复现
复现要求:看wp做一遍,自己做一遍,第二天再做一遍。(一眼看出来就跳过) 目录 [LitCTF 2024]浏览器也能套娃? [LitCTF 2024]一个....池子? [LitCTF 2024]高亮主题(划掉)背景查看器 [LitCTF 2…...
Elasticsearch:跨集群使用 ES|QL
警告:ES|QL 的跨集群搜索目前处于技术预览阶段,可能会在未来版本中更改或删除。Elastic 将努力解决任何问题,但技术预览中的功能不受官方 GA 功能的支持 SLA 约束。 使用 ES|QL,你可以跨多个集群执行单个查询。 前提: …...
学习笔记4:docker和k8s选择简述
docker和 k8s 占用资源 使用客户体量Docker 和 Kubernetes(K8s)都是流行的容器化技术,但它们在资源管理和使用上有一些不同。以下是关于两者资源占用和使用客户体量的详细比较,基于具体数据和信息: Docker 资源占用…...
关于锁策略
在Java中对于多线程来说,锁是一种重要且必不可少的东西,那么我们将如何使用以及在什么时候使用什么样的锁呢?请各位往下看 悲观锁VS乐观锁 悲观锁: 在多线程环境中,冲突是非常常见的,所以在执行操作之前…...
昇思25天学习打卡营第3天|基础知识-数据集Dataset
目录 环境 环境 导包 数据集加载 数据集迭代 数据集常用操作 shuffle map batch 自定义数据集 可随机访问数据集 可迭代数据集 生成器 MindSpore提供基于Pipeline的数据引擎,通过数据集(Dataset)和数据变换(Transfor…...
C++11新特性——智能指针——参考bibi《 原子之音》的视频以及ChatGpt
智能指针 一、内存泄露1.1 内存泄露常见原因1.2 如何避免内存泄露 二、实例Demo2.1 文件结构2.2 Dog.h2.3 Dog.cpp2.3 mian.cpp 三、独占式智能指针:unique _ptr3.1 创建方式3.1.1 ⭐从原始(裸)指针转换:3.1.2 ⭐⭐使用 new 关键字直接创建:3.1.3 ⭐⭐⭐…...
“微软蓝屏”全球宕机,敲响基础软件自主可控警钟
上周五,“微软蓝屏”“感谢微软 喜提假期”等词条冲上热搜,全球百万打工人受此影响,共同见证这一历史性事件。据微软方面发布消息称,旗下Microsoft 365系列服务出现访问中断。随后在全球范围内,包括企业、政府、个人在…...
【Linux C | 网络编程】进程间传递文件描述符socketpair、sendmsg、recvmsg详解
我们的目的是,实现进程间传递文件描述符,是指 A进程打开文件fileA,获得文件描述符为fdA,现在 A进程要通过某种方法,传递fdA,使得另一个进程B,获得一个新的文件描述符fdB,这个fdB在进程B中的作用…...
高并发内存池(六)Page Cache回收功能的实现
当Page Cache接收了一个来自Central Cache的Span,根据Span的起始页的_pageId来对前一页所对应的Span进行查找,并判断该Span,是否处于使用状态,从而看是否可以合并,如果可以合并继续向前寻找。 当该Span前的空闲Span查…...
浅析JWT原理及牛客出现过的相关面试题
原文链接:https://kixuan.github.io/posts/f568/ 对jwt总是一知半解,而且项目打算写个关于JWT登录的点,所以总结关于JWT的知识及网上面试考察过的点 参考资料: Cookie、Session、Token、JWT_通俗地讲就是验证当前用户的身份,证明-…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
2.3 物理层设备
在这个视频中,我们要学习工作在物理层的两种网络设备,分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间,需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质,假设A节点要给…...
Linux-进程间的通信
1、IPC: Inter Process Communication(进程间通信): 由于每个进程在操作系统中有独立的地址空间,它们不能像线程那样直接访问彼此的内存,所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...
