首页 > 其他分享 >省选05. 线性代数

省选05. 线性代数

时间:2022-12-24 09:23:42浏览次数:45  
标签:frac 05 省选 sum 5n 线性代数 线性 复杂度 deg

P6772 [NOI2020] 美食家

先假设没有美食节,容易得到一个矩阵优化的 dp。

加上美食节过后分成 \(k\) 段考虑,每段分别矩阵快速幂,时间复杂度为 \(O((5n)^3k\log T)\)。

这并不能通过本题。

可以思考快速幂优化乘法的本质,预处理出转移矩阵的 \(2\) 的幂。

原本快速幂是将一堆 \(5n\times 5n\) 的矩阵乘起来,最后再乘一个 \(1\times 5n\) 的矩阵,每一段的时间复杂度达到 \(O((5n)^3\log T)\)。

可以考虑使用结合律交换顺序,每一段分别用 \(1\times 5n\) 的矩阵乘一堆 \(5n\times 5n\) 的矩阵,这样复杂度降为 \(O((5n)^2\log T)\)。

因此总复杂度降为 \(O((5n)^3\log T+(5n)^2k\log T)\)。

CF113D Museum

设 \(f(u,v)(u\neq v)\) 表示分别从 \(u\),\(v\) 出发,在 \(s\) 相遇的概率。

设 \(deg(u)\) 表示 \(u\) 的度数。

假设从 \((u,v)\) 走一条边到 \((i,j)\)。

\[f(u,v)=p(u)p(v)f(u,v)+\sum_{i\ne u}f(i,v)\frac{1-p(u)}{deg(u)}p(v)+\sum_{j\neq v}f(u,j)\frac{1-p(v)}p(u){deg(v)}+\sum_{i\neq u}\sum_{j\neq v}f(i,j)\frac{(1-p(u))(1-p(v))}{deg(u)deg(v)} \]

移项得

\[(1-p(u)p(v))f(u,v)-\sum_{i\ne u}f(i,v)\frac{1-p(u)}{deg(u)}p(v)-\sum_{j\neq v}f(u,j)\frac{1-p(v)}{deg(v)}p(u)-\sum_{i\neq u}\sum_{j\neq v}f(i,j)\frac{(1-p(u))(1-p(v))}{deg(u)deg(v)}=0 \]

可以发现 \(f(s,s)=1\),对于不等于 \(s\) 的 \(i\),\(f(i,i)=0\)。

因此,这 \(n^2-n\) 个方程每个右边都是一堆关于 \(f(i,i)\) 的线性组合。

左边有 \(n^2-n\) 个未知数,右边有 \(n\) 个参数,对于左边高斯消元即可。

注意特判起点相同的情况。

P2973 [USACO10HOL]Driving Out the Piggies G

对于需要使用高斯消元解决的 dp 问题,必须保证边界值好确定。

设 \(f(u)\) 表示经过 \(u\) 点的期望次数。

\[f(u)=[u=1]+\sum_{u\to v}f(v)\frac{1-\frac{p}{q}}{deg(v)} \]

最后,\(i\) 点的答案为 \(f(i)\frac{p}{q}\)。

CF24D Broken robot

设 \(f(i,j)\) 表示从 \((i,j)\) 开始走,走到第 \(n\) 行的期望步数。

\(f(n,i)=0\)。

枚举 \((i,j)\) 可能走到哪里,设走到 \((x,y)\) 的概率为 \(p\),答案为

\[f(i,j)=1+\sum_{x,y}f(x,y)p \]

直接高斯消元复杂度是 \(O(n^6)\)。

但是由于不能往上走,因此可以一行一行地高斯消元,复杂度变为 \(O(n^4)\)。

再仔细观察矩阵发现系数都在主对角线附近,因此可以做到 \(O(n^2)\)。

UVA12177 First Knight

设 \(f(i,j)\) 表示从 \((i,j)\) 走到 \((n,m)\) 的期望步数。

\(dp(n,m)=0\)。

\[f(i,j)=1+\sum_{x,y}f(x,y)p((x,y)\rightarrow(i,j)) \]

暴力高斯消元复杂度为 \(O(n^3m^3)\)。

将坐标建立与编号的映射 \((i,j)\longrightarrow (n-i)m+m-j+1\)。

可以考虑只保留上三角矩阵,即消掉下三角矩阵。

对于一个未知数 \(i\),只需要遍历 \((i,i)\) 到 \((i+m,i+2m)\) 的矩阵就行了,时间复杂度优化为 \(O(nm^3)\)。

P7016 [CERC2013]Captain Obvious and the Rabbit-Man

构造多项式

\[\begin{aligned} A(x) &=(x-F_1)(x-F_2)\cdots(x-F_k)\\ &= x^k+b_1x^{k-1}+b_2x^{k-2}+\cdots +b_k \end{aligned} \]

\[A(F_i)=F_i^k+b_1F_i^{k-1}+b_2F_i^{k-2}+\cdots +b_k=0 \]

对 \(i=1\to k\) 求和

\[\sum_{i=1}^kA(F_i)=\sum_{i=1}^kF_i^k+b_1\sum_{i=1}^kF_i^{k-1}+b_2\sum_{i=1}^{k}F_i^{k-2}+\cdots+b_{k-1}\sum_{i=1}^kF_i+b_kk=0 \]

发现这样似乎没法用到题目给出的 \(p_i\),于是可以考虑先对 \(A(F_i)\) 乘 \(a_i\) 再求和

\[\sum_{i=1}^kA(F_i)a_i=\sum_{i=1}^kF_i^ka_i+b_1\sum_{i=1}^kF_i^{k-1}a_i+b_2\sum_{i=1}^{k}F_i^{k-2}a_i+\cdots+b_{k-1}\sum_{i=1}^kF_ia_i+b_k\sum_{i=1}^ka_i=0 \]

\[\sum_{i=1}^kA(F_i)a_i=p_k+b_1p_{k-1}+b_2p_{k-2}+\cdots+b_{k-1}p_1+b_k\sum_{i=1}^ka_i=0 \]

推到这里还是推不动,再在前面求和之前乘个 \(F_i\)

\[\sum_{i=1}^kA(F_i)a_iF_i=p_{k+1}+b_1p_k+b_2p_{k-1}+\cdots+b_kp_1=0 \]

于是

\[p_{k+1}=-\sum_{i=1}^kb_ip_{k-i+1} \]

\(O(k^2)\) 解出 \(b_i\),即可计算答案。

CF963E Circles of Waiting

\(f(x,y)\) 表示从 \((x,y)\) 出发,走到距离大于 \(R\) 的点的期望步数。

如果 \(x^2+y^2>R^2\),\(f(x,y)=0\)。

\[f(x,y)=1+f(x-1,y)p_1+f(x,y-1)p_2+f(x+1,y)p_3+f(x,y+1)p_4 \]

暴力高斯消元时间复杂度为 \(O(n^6)\)。

考虑使用主元法。

将纵坐标从上到下,横坐标从左到右依次编号,取每个纵坐标最左边的横坐标为主元。

\[f(x+1,y)=\frac{f(x,y)-f(x-1,y)p_1-f(x,y-1)p_2-f(x,y+1)p_4-1}{p_3} \]

可以达到 \(O(n^3)\)。

P3211 [HNOI2011]XOR和路径

按位处理。

设 \(f(u)\) 表示从 \(u\) 出发到 \(n\),这一位的异或和为 \(1\) 的概率。

\[f(u)=\sum_{u\to v}\frac{[w=0]f(v)+[w=1](1-f(v))}{deg(u)} \]

注意判断自环,自环的边只能连一次。

CF895C Square Subsets

完全平方数只与质因子的奇偶有关,小于等于 \(70\) 的质数只有 \(19\) 个,因此可以把每个数分解质因数后用二进制表示。

两个数想成等价于异或,原问题等价于异或和为 \(0\) 的真子集数。

假设线性基插入的元素个数为 \(cnt\),那么答案为 \(2^{n-cnt}-1\)(线性基的基底异或一定不为 \(0\))。

P4869 albus就是要第一个出场

对于一个已经确定的线性基,新加入一个能被基底表示的数,会使得所有能被表示的数统一乘 \(2\)。

于是问题就转化为查询一个数在线性基中的排名。

P5607 [Ynoi2013] 无力回天 NOI2017

很明显是线段树 + 线性基。

但线性基无法下传标记,于是考虑差分。

设 \(a_{i-1}\oplus b_i=a_i\),每次只需要支持单点修改即可。

可以发现 \(a_{l\rightarrow r}\) 组成的线性基与,\(a_l\) 和 \(b_{l+1\rightarrow r}\) 组成的线性基相同(考虑 \(a_i\) 的定义来证明)。

于是这道题可以在 \(O(n\log n\log^2 V)\) 解决。

CF845G Shortest Path Problem?

图中的环可以任意添加,于是可以把所有环加入线性基中。

其实 \(1\) 到 \(n\) 的路径也可以任意选择,因为如果存在一条更优的路径,它会与原路径成环,一定会被加入线性基中。

CF1299D Around the World

发现边权值只达到 \(31\),爆搜发现线性基的种类只有 \(374\)。

考虑先将 \(1\) 连出去边删掉,可以得到很多连通块,沿用 CF845G 的方法,把每个连通块的环加入线性基中,如果存在一个环的权值不能加入线性基中,那么这个连通块一定不能与 \(1\) 相连。

因为不存在长度大于 \(3\) 的简单环,因此 \(1\) 向这些连通块要么连一条边,要么连两条边。

设 \(dp(i,j)\) 表示前 \(i\) 的连通块中,线性基为 \(j\) 的方案数,分类转移即可。

标签:frac,05,省选,sum,5n,线性代数,线性,复杂度,deg
From: https://www.cnblogs.com/yanchengzhi/p/17002017.html

相关文章

  • 省选06. 分治
    CF1442DSum设\(dp(i,j)\)表示前\(i\)个数组选\(j\)个元素的最大值。\[dp(i,j)=\max_{k=0}^jdp(i-1,k)+sum(i,k)\]因为数组内的元素单调不降,因此有一个结论,只有一......
  • 省选03. 树上问题
    P2664树上游戏首先,将贡献拆成每种颜色对每个点的贡献。考虑已经选择了一种颜色,将这些颜色的点和所对应边全部删去,就得到了很多连通块。假设其中一个连通块的大小为\(s......
  • 省选04. 数论
    P4571[JSOI2009]瓶子和燃料先对两个容量分别为\(a\),\(b\)的瓶子考虑。可以发现,无论是倒入还是倒出,体积都是\(a\)或\(b\)的整数倍。因此可以考虑求\(ax+by\)的......
  • 每日食词—day058
    topup加满、装满、充值certificaten. v.凭证、证书、认证、证明书persistv.坚持、持续、保持、固执manuallyadv.手动、手工地、人工、用手kerneln.......
  • 力扣-105-从前序与中序遍历序列构造二叉树/剑指Offer-07
    基本步骤是这样:先看先序序列,可以确定根节点,然后在中序遍历中就可以将二叉树划成左子树和右子树两拨对左右子树递归上述步骤好像直到怎么遍历二叉树,却对怎么重建二叉树......
  • 每日食词—day057
    gendern.性别freeadj. adv. v. n.空闲的、自由的、自由、免费、释放、无、空闲、闲置librariesn.图书馆、(程序)库、文件库、函数库compilingn. v.编译......
  • Spring Security系列教程05--实现Form表单认证
    实现Form表单认证前言在上一章节中,​​一一哥​​带大家认识了SpringSecurity中的第一种认证方式,但是这种基本认证的方式,UI效果不漂亮,安全性也很差,好像一无是处的样子,那么......
  • Day17_05_SpringCloud教程之Eureka实战
    SpringCloud之Eureka实战一.版本说明本案例采用的SpringBoot版本为2.0.3.RELEASE,SpringCloud版本为Finchley.RELEASE.二.创建主工程1.项目结构主工程目录结构如下图所......
  • Day07_05_分布式教程之分布式事务详解
    分布式事务详解一.分布式事务的概念随着分布式计算的发展,事务在分布式计算领域也得到了广泛的应用.在单机数据库中,我们很容易能够实现一套满足 ​​ACID​​ 特性的事......
  • SpringBoot2.x系列教程19--Web开发05之XML方式实现SSM整合
    SpringBoot系列教程19--Web开发05之XML方式实现SSM整合作者:一一哥注意:本系列教程案例继续在之前的基础上进行编写!SpringBoot可以帮助我们快速搭建一个SSM框架环境,那么该怎......