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

CF691E Xor-sequences

CF691E Xor-sequences

[10月9日的茶](Problem - 691E - Codeforces)

计数问题,只有相邻元素有约束,k很大,考虑矩阵快速幂dp

因为只有相邻元素有约束,所以转移只用看某序列最后一个元素,设 \(f[i][j]\) 为长度为 \(i\) 的序列,最后一个元素是 \(a_j\) 的个数

对于序列 \(b\) 相邻元素的 \(b_i\)\(b_{i+1}\) 的的限制只有 \(3 \mid b_i \bigoplus b_{i+1}\)

可以考虑构造矩阵 \(M\) 描述 \(a_i\)\(a_j\) 的转移关系

\(M_{ij} = 1\)\(3 \mid a_i \bigoplus a_j\)

\(M_{ij} = 0\)\(3 \nmid a_i \bigoplus a_j\)

快速幂计算 \(f[i]M^{k-1}\) 即可

代码

注意矩阵运算不满足交换律 (\(res \times qpow(M, n)\) 处)

\(\_\_ popcount((ull))\) 处要开 \(ull\) 而不能是 \(unsigned\)

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

相关文章:

  • LCPC12E - Johnnys Empire 题解
  • 中微笔记-cp.1 技术
  • P1896 [SCOI2005] 互不侵犯小总结
  • 美国能源部《生成式人工智能参考指南》解读
  • 分析InfluxDB中读取时CPU飙升
  • win10系统访问smb服务时提示密码错误
  • 《小说课》读书笔记
  • 2025-10-11?
  • 高二停课周记(信息学竞赛) Week1
  • AtCoder Beginner Contest 427 ABCDEF 题目解析
  • zju博士资格考试考前复习(微分方程方向)ode 部分
  • 测试一下博客功能
  • AI如何改变芯片设计
  • NOIP 2024
  • 2025/10/11
  • 好玩热门的switch游戏推荐【PC+安卓】塞尔达传说:王国之泪|v1.4.2整合版|官方中文| 附switch模拟器
  • 十年运维工程师总结
  • 运动控制教学——5分钟学会Dijkstra与A*搜索算法!(附仿真视频及代码) - 教程
  • ffplay数据结构解析
  • CNN 发展历程
  • FileX和ThreadX精简版
  • ue4素材场景 - MKT
  • 阅读《构建之法》的思考与问题
  • 实验报告5(链栈基本操作,数制转换,匹配算法,伴舞问题)
  • 阅读和提问作业1:《构建之法》提问
  • 企业推行OKR中层领导关注的10个关键问题及解决方案
  • 初四夜间/休息日安排
  • AWS自然语言处理技术实战指南
  • 多线程
  • 三级模式