首页 > 其他分享 >P4894 题解

P4894 题解

时间:2023-12-31 21:59:58浏览次数:26  
标签:color 题解 backslash purple vmatrix green red P4894

实际上,这是两个向量的叉积已经是其他题解说烂了的。这里只是给出一个容易记忆 \(dim\le 3\) 的行列式的值的办法。

我们以 \(3\) 维行列式为例子,假设为

\[\begin{vmatrix} a & b & c\\ i & j & k\\ o & p & q \end{vmatrix} \]

我们有一个神奇的方法来记忆这个行列式的求值。
首先从左上向右下打斜线,出格的部分从左向右重新打。相同颜色的斜线代表同一条斜线的话,应该是这样子的:

\[\begin{vmatrix} {\color{red} \backslash} a & {\color{green} \backslash}b & {\color{purple} \backslash}c\\ {\color{purple} \backslash}i & {\color{red} \backslash} j & {\color{green} \backslash}k\\ {\color{green} \backslash}o & {\color{purple} \backslash}p & {\color{red} \backslash} q \end{vmatrix} \]

我们把斜线上的数相乘再相加,得到 \(ajq+bko+cip\)。

同理,我们从右向左打斜线:

\[\begin{vmatrix} {\color{red} \backslash} a & {\color{green} \backslash}b & {\color{purple} \backslash}c\\ {\color{green} \backslash}i & {\color{purple} \backslash} j & {\color{red} \backslash}k\\ {\color{purple} \backslash}o & {\color{red} \backslash}p & {\color{green} \backslash} q \end{vmatrix} \]

同样得到 \(akp+bqi+coj\)。把两个式子相减即可得到答案。

二维行列式是完全类似的。只是可惜,这个规律在更高阶的行列式并不适用。

标签:color,题解,backslash,purple,vmatrix,green,red,P4894
From: https://www.cnblogs.com/Piggy424008/p/17938055/solution-p4894

相关文章

  • AT_arc127_a 题解
    在HL群里吃瓜,顺手写一篇题解。第一眼必定是数位dp,可是这会使原题难度反而升高了。相对而言,我们要是枚举前缀\(1\)的长度,然后寻找对答案有贡献的区间,此问题是很容易的。同时我们不难发现,前缀\(1\)长度为\(l\)的所有有贡献的数字即为\(\foralli\in[l,16],(\sum_{i=0}^l1......
  • CF1239E 题解
    因为懒得用bitsetMLE了。所以各位想A这题的别偷懒用布尔数组!本题解意在解释如何做类似的dp题,而不在于解释本道题做法的具体推导,只是给出一个思路。我们观察发现,题目想让我们最小化一个最大值。我们并不能枚举每种方案去找最大值再取\(\min\),这样复杂度爆炸而且没有前途......
  • AGC034F 题解
    FWT入门题,很适合我这样的蒟蒻。首先我们可以轻松的根据转移条件写出来一个优美的函数\(T(i)=1+\sum_{j\oplusk=i}a_kT(j)\),边界为\(T(0)=0\)。这个方程属于转移带环的DP,处理方法一般是高斯消元,在这道题里会T飞。但是我们又注意到后边是一个美丽的异或卷积,因此可以考虑用......
  • P6256 题解
    我认为,这道题是我学OI历史以来做过的最难写,最难受,最变态,最不可做,最怀疑人生的题。然后还莫名其妙遇见了!给出一种时间复杂度略劣于ix35的做法。因为本人码力不是很好,因此认为这道题讲讲代码写法也很必要。题意就是给一些线段上戳洞,使得对于给定的一个区间\([l,r]\),从无穷远......
  • P9438 题解
    对于一次询问,相当于在考虑整数\(\frac{n}{x}\)变为\(1\)的方案数。进一步的,这相当于给定一个数列\(c_0\cdotsc_k\),每一次可以减小任意位的任意值,但不能空选,问方案数,这里“空选”指的是不选任何一个数。先考虑允许空选的时候应该怎么做,令\(f(x)\)代表正好走了\(x\)步变......
  • P4528 题解
    这篇题解并不做任何形式上的理论推导,而是在于引导像我一样的蒟蒻,如何在遇到这样的题时,不会陷入数据结构暴力分别求三种形态的深渊里无法自拔。看到这道题我们的第一想法应该是把三种形态的数量都求出来,如果可以的话,这题马上就秒掉了。那么我们尝试着去求——比较简单的可能是高......
  • 一些数 题解
    首先我们考察LIS长度为\(n-1\)的数列的性质。可以发现,这必定是\(1,2,3,\cdots,n\)中拎出一个不听话的元素甩到其他地方去,剩下的元素依次补齐所构成的。这意味着,最多只有一个元素满足\(a_i-i\ge2\),更具体的,不考虑只对邻项交换的排列(即形如\(1,2,3,\cdots,i,i-1,\cdots,n\)),......
  • 自出题题解
    U288469Piggy算路程显然是简单贪心。黄。U306825Piggy数编号先推式子。令\(L(n,k)\)为最长区块长度为\(k\)的方案数,则\(Ans=\sum_{i=0}^n\limits{L(n,i)}\timesk\)。下面转为求\(L(n,k)\)。我们考虑可能的区块长度分别为多少。那么就相当于我们要枚举所有的长度在......
  • CF1438F 题解
    如果能想到这道题用随机化,想来这道题的解法就显然了。但是为什么这道题一定要随机呢?我们考虑一棵完美二叉树,编号随机。这棵树的熵毛估估一下应该是\(O(\log^nn)\)的,但是一次询问的话,考虑每次只能得到三个点的偏序关系为某几种情况的一种,这个熵是很小的,只有\(O(\logn)\),对减......
  • P7400 题解
    P7400,一个有趣的博弈论。下面称Paula和Marin都执行一轮操作的“一整轮”为一个周期。Sub1:\(n\le100\)我们采用\(O(n^2\timesn)=O(n^3)\)的DP即可。这里略去具体实现。Sub2:边的颜色均为洋红这意味着两人都可以走过任意一条边。考虑两方如何对对方进行“围追堵截”......