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

qoj.6555 Sets May be Good 做题记录

此处应该有「笔记」。link

似乎很难有多项式做法,但是一个强大的线性代数能巧妙地解决这个问题。

原题相当于求解

\[\sum\limits_{x\in \mathbb F_2^n} \left [\sum\limits_{(i, j)\in E} x_ix_j \equiv 0 \pmod 2 \right] \]

我们很容易将其表示为

\[\begin {aligned} \sum\limits_{x\in \mathbb F_2^n} \left [\sum_{i = 1} ^ n \sum_{j = 1} ^ n A_{i, j}x_ix_j \equiv 0 \pmod 2 \right] &= \sum\limits_{x\in \mathbb F_2^n} \left [x^TAx \equiv 0 \pmod 2 \right] \end {aligned} \]

\(Q\) 为一个模 \(2\) 意义下的可逆矩阵,那么 \(Qx\) 取遍 \(\mathbb F_2^n\),可以表示为

\[\begin {aligned} \sum\limits_{x\in \mathbb F_2^n} \left [(Qx)^TA(Qx) \equiv 0 \pmod 2 \right] &= \sum\limits_{x\in \mathbb F_2^n} \left [x^TQ^TAQx \equiv 0 \pmod 2 \right] \\ &= \sum\limits_{x\in \mathbb F_2^n} \left [x^T(Q^TAQ)x \equiv 0 \pmod 2 \right] \end {aligned} \]

\(Q/Q^T\) 可以表示为若干个初等变换的矩阵乘积,我们

http://www.hskmm.com/?act=detail&tid=31188

相关文章:

  • 结构化数据自动生成文本技术解析
  • CSharp: Aspose.CAD 25.10 Convert DWG and DXF to PDF
  • vtk学习——Pipeline
  • 长沙四大名校x东方project
  • Rust 的英文数字验证码识别系统设计与实现
  • IOS开发 - UIViewController 界面控制基类解析
  • SpringBoot运维实用篇(YW-1.SpringBoot程序的打包与运行,YW-2.配置高级,YW-3.多环境开发,YW-4.日志) - a
  • CSP-S模拟31
  • Fortran 实现英文数字验证码识别系统
  • 10.14 NOIP 模拟赛 T1. HappyLovelyEveryday!
  • CSP-J 2025 入门级模拟赛 Day6 复盘 B. 罐の水表
  • 10.14每日总结
  • 四边形不等式
  • 20251014 杂题
  • 二叉树的遍历
  • SQL在智能自动化业务场景中的应用 - Irving11
  • 拼接字符串要求字典序最小
  • 高级语言作业第一次随笔
  • C#实现开机自启动应用多种方式
  • 日志|二叉树|110平衡二叉树|111二叉树的最大深度|199二叉树的右视图
  • Chrome在Speedometer 3.1创下历史最高分,为用户节省数百万小时
  • 西电CTF平台——Moectf 2025 WriteUP
  • [笔记]并查集进阶(带权、扩展域、带删除)
  • 20251013 模拟赛 总结
  • 什么是反应式编程 - 详解
  • SDL3和其附属的编译记录
  • Qwen多模态系列模型笔记—Qwen2-VL
  • WPF 调用 ChangeWindowMessageFilterEx 修改指定窗口 (UIPI) 消息筛选器的用户界面特权隔离
  • 实验1 现代C++基础课程
  • 牙科诊所借力AI营销4个月创收13万