首页 > 其他分享 >QOJ #8473. Matrices and Determinants

QOJ #8473. Matrices and Determinants

时间:2024-06-21 21:31:32浏览次数:26  
标签:Determinants gcd 矩阵 det mid 构造 frac Matrices QOJ

唉,不会线性代数了,做了三个小时。

为了求行列式,显然要先把 \(A\) 消成上三角矩阵,记作 \(A'\)。我们显然可以在操作 \(A\) 的时候求出将 \(A\) 消成 \(A'\) 的操作矩阵 \(M\),则我们可以构造 \(A'=B'C'\),再将 \(B'\) 乘上 \(M^{-1}\) 就可以得到原来的 \(B\)。

判掉 \(A\) 的行列式不是完全平方的情况,记 \(\det(A)=k^2\),则我们需要构造 \(\det(B')=k\)。\(\det (C)\) 不用特别管,因为 \(B\) 的限制满足了根据 \(\det(BC)=\det(B)\det(C)\) 就会自动满足 \(C\) 的限制。

这样直接构造还是很难构造,我们考虑让 \(B,C\) 都是上三角矩阵,这样就比较容易。令 \(B_{n,n}=\gcd(n,A_{n,n}),C_{n,n}=\frac{A_{n,n}}{B_{n,n}}\),然后递归构造 \(n-1\) 阶行列式为 \(\frac{k}{B_{n,n}}\) 的矩阵。

构造出来之后考虑 \(i\) 从大到小依次确定 \(B_{i,n}\) 和 \(C_{i,n}\) 的取值,直接模拟矩阵乘法会得到一个不定方程形如 \(B_{i,n}C_{n,n}+C_{i,n}B_{i,i}=w\),我们需要找到一组解。

直接 exgcd 可以处理 \(\gcd(B_{i,i},C_{n,n})\mid w\) 的情况,但是可以发现,\(\gcd(B_{i,i},C_{n,n})=1\)。假设其有约数 \(p\)。\(p\mid B_{i,i}\) 说明 \(p\mid \frac{k}{\gcd(k,A_{n,n})}\),而 \(p\mid C_{n,n}\) 说明 \(p\not\mid \frac{k}{\gcd(k,A_{n,n})}\),矛盾,因此其没有最大公约数。

时间复杂度 \(O(Tn^3)\),但是值域会比较大。

submission

标签:Determinants,gcd,矩阵,det,mid,构造,frac,Matrices,QOJ
From: https://www.cnblogs.com/275307894a/p/18261364

相关文章

  • QOJ1285 Stirling Number
    QOJ传送门因为\(x^{\overlinep}\equivx^p-x\pmodp\),所以设\(n=pq+r\),其中\(r\in[0,p-1]\),则有:\[\begin{aligned}x^{\overlinen}&=(\prod\limits_{i=0}^{q-1}(x+ip)^{\overlinep})(x+pq)^{\overliner}\\&=(x^p......
  • QOJ #1285.Stirling Number
    一道非常厉害的题目。题意求:\[\sum_{i=0}^{m}c(n,i)\modp\]其中\(c(n,i)\)为无标号第一类斯特林数,且有\(n,m\le10^{18},p\le10^6\)。Sol考虑一个性质:\[x^{\overlinep}\equivx^p-x\modp\]证明比较简单,考虑费马小定理,\(x^p\equivx\modp\)。而\(x,x+1,\cdots,x+......
  • QOJ 7008 另解
    文中符号:\(\operatorname{Period}(s)\):字符串\(s\)的周期集合。\(\operatorname{Per}(s)\):字符串\(s\)的最小周期。循环节:\(x\in\operatorname{Period}(s)\)且\(x|\operatorname{len}(S)\)。\(\operatorname{Cyc}(s)\):\(s\)的最小循环节。\(\operatorname{endpos}(......
  • QOJ 4824 Bracket-and-bar Sequences
    考虑到这个实际上没有特别好的表示方法。不如从\(n\le25\),猜想合法的序列数量不多。考虑对这个计数。类似于合法括号序计数,考虑把串拆为\(\texttt{(}\cdots\texttt{|}\cdots\texttt{)}\cdots\)来考虑。那么令\(f_i\)表示\(i\)对\(\texttt{(|)}\)组成的序列的数量。......
  • QOJ 6537 One, Two, Three
    令原题中的\(1,2,3\)分别对应\(0,1,2\)。一种贪心想法就是直接记录\(0,2,01,21,012/210\)的个数然后直接配对。但是考虑到如果当前的\(1\)前面既有\(0\)也有\(2\),后面不管是\(0\)还是\(2\)都能配对。但是按照先前的策略肯定会成为\(01\)或\(21\),这......
  • qoj1138 Counting Mushrooms
    交互题。有一个隐藏的01序列\(a\),你只知道\(a\)的长度,并记为\(n\)。保证\(a_1=0\)。你可以执行以下操作:询问一个序列\(b\),满足两两不同且长度在\([2,1000]\)之间。交互库会返回\(\sum[a(b_i)\not=a(b_{i+1})]\)。请在\(226\)次操作内求出\(a\)中\(0\)......
  • qoj3082 Ascending Matrix 题解
    题目链接点击打开链接题目解法不考虑第\(a_{r,c}=v\)的限制怎么求?我们把条件形式化一下,发现\(k\)个区域的颜色可以表示成轮廓线的形式,即第\(i-1\)条到第\(i\)条轮廓线之间的格点颜色为\(i\)问题变成找到\(k-1\)条互不穿过的路径,起点为\((1,m)\),终点为\((n,1)\)......
  • QOJ5717
    非常好题目,拜谢Itst。不过如果我去考这场估计就哈哈了。\(k=3\)都能卡。还是要避免一条路走到黑啊。懂得变通。\(k=1\)是送的。\(k=2\)较为平凡,只需要将相对大的、相对小的各放一起。\(k=3\)不简单了。首先二分答案\(mid\),经过800万年转换视角,钦定顺序之类的尝试应......
  • QOJ2559
    区间维护类的小(?)DS题。感觉我不怎么会。题意目的明确,就是要动态维护每个区间能覆盖的范围。看一看,感觉题目里的条件很神秘,不知道怎么用。不过可以根据特殊性质推出一个性质:存在包含关系一定先选内部。一开始的思路是用区间互相影响计算,但这个非常复杂,且非常假。在写暴力的时候......
  • QOJ #1280.Fibonacci Partition/Fibonacci性质大杂烩
    QOJ#1280.FibonacciPartition(为什么布置的作业题没有任何可见AC记录啊/kk)拿下了QOJ上的用户首杀(同时目前也是QOJ可见的submission中唯一一个过掉这个题的,另一个是vjudge上我的提交)。也许是这个题实在是太冷门了,但是从Fibonacci-Lucas数列的性质应用上是一道非常......