2020-07-13 10:50 华中科技大学 C++

关注

[NowCoder5666D]Quadratic Form

Quadratic Form

https://ac.nowcoder.com/acm/contest/5666/D

题意

$\begin{aligned} \max_x &\quad b^Tx\\ {\rm s.t.} &\quad x^TAx-1\le0 \end{aligned}$

求 $(b^Tx)^2\mod 998244353$ .

$A$ 为 $n\times n$ 的对称矩阵， $b,x\in\mathbb{R}^n$
$n\le200,0\le|A_{i,j}|,|b_i|\le10^9$
$\forall x\in\mathbb{R}^n/\ \{\boldsymbol0\},x^TAx>0$
$\det(A)\not\equiv0\pmod{998244353}$

题解——我的博客

设兰格朗日函数 $\mathcal{L}(x,\lambda)=b^Tx+\lambda(x^TAx-1)$ ，根据向量求导法则，有

$\frac{\partial\mathcal{L}}{\partial x}=b+\lambda(A+A^T)x=b+2\lambda Ax$

令 $\displaystyle\frac{\partial\mathcal{L}}{\partial x}=0$ ，可得 $\displaystyle x=-\frac{A^{-1}b}{2\lambda}$ 。由KKT条件： $\lambda(x^TAx-1)=0,\lambda\le0$ 。将 $x$ 带入得

$\begin{aligned} &\lambda[(-\frac{A^{-1}b}{2\lambda})^TA(-\frac{A^{-1}b}{2\lambda})-1]=0\\ \Rightarrow&\qquad b^T(A^{-1})^TAA^{-1}b=4\lambda^2,\quad (A^{-1})^T=A^{-1}\\ \Rightarrow&\qquad \lambda=-\frac12\sqrt{b^TA^{-1}b} \end{aligned}$

故

$b^Tx=b^T(-\frac{A^{-1}b}{2\lambda})=-\frac{b^TA^{-1}b}{\sqrt{b^TA^{-1}b}}=\sqrt{b^TA^{-1}b}$

最终的答案为 $(b^Tx)^2=b^TA^{-1}b$ 。用高斯消元求出 $A$ 的逆再相乘即可。

单组数据时间复杂度 $O(n^3)$

全部评论

推荐最新楼层

05-16 11:04

南京邮电大学 Java

24届半年经验-Java面经-华OD

一、背景24届本科，专业电子信息工程，毕业后起初打算二战，复习到10月份感觉进度太慢，风险太大于是放弃考研开始找工作，通过同学认识的栗栗姐。二、机考 机考300分第一题做过的原题计算三叉搜索树的高度不算难第二题成绩单相关的一道题没做出来第三题任务最优调度想了很久才做出来三、综测 综测就是选保持积极向上的选项，谦虚不突出个人风格的选项，要注意前后选项要尽量保持一致。四、HR面试就简单聊了一下，基本10分钟左右就结束了，感觉没说什么五、技术一面 基本围绕我的项目展开很多问的是我简历写的项目相关的问题，然后再根据项目涉及的技术逐渐的深入问，直到你不会为止，中间还给了一道sql表关联的题不过我没有做出...

查看16道真题和解析

点赞评论收藏

分享

昨天 16:11

长沙理工大学 Java

📍面试公司：腾讯云智一面💻面试岗位：后台开发❓面试问题：1.线程池怎么用的，执行流程，参数配置2.项目动态线程池组件怎么实现的3.缓存逻辑过期，逻辑判断了过期和设置过期时间这种有啥区别（认为逻辑过期没啥用）。4.Sql优化，索引优化。联合索引中哪些列放前面（怎么排序）。select b (a,b,c)走没走索引。5.项目拷打。6.http27.https握手怎么实现的8.tcp拥塞控制，closewait状态什么时候出现9.虚拟内存和物理内存10.concurrentHashMap11.reentrantlock底层实现（深挖源码，tryAcquire怎么实现）12.二叉树哪些遍历方法13...

腾讯云智研发一面178人在聊

查看16道真题和解析面试问题记录

点赞评论收藏

分享

03-28 16:51

门头沟学院全栈开发

美团也接受零基础后端转前端？

我也想要这个机会啊

zzzzz231：后端卷🐶的阴谋罢了

点赞评论收藏

分享

04-17 23:44

湖南农业大学后端

现在HR们的话术越来越离谱了

WillingLing：

查看图片

点赞评论收藏

分享

05-19 07:37

同济大学 ARM工程师

AI现在真能代替程序员了

微软裁员真的跟这个有关吗？我以为只是微软在降本增效。有点离谱。 全网最受欢迎的嵌入式面经面经一共32篇文章，12w+字数，包含全部最新的面试必问考点，4.7w+同学学习，2800+订阅，非常适合在找工作面经薄弱的同学，3000+订阅还会涨价，提前订阅提前享受，持续更新中。原帖链接：https://www.nowcoder.com/creation/manager/columnDetail/MJNwoM

投递微软等公司6个岗位 > 这些公司卡简历很严格大学最后一个寒假，我想……

点赞评论收藏

分享

评论

4

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 毕业季，给职场新人一些建议 #

26776次浏览 458人参与

# 你的房租占工资的比例是多少？ #

23086次浏览 255人参与

# 我的求职总结 #

30011次浏览 501人参与

# 计算机专业还有必要去大厂卷吗 #

20641次浏览 109人参与

# 我的实习日记 #

2444509次浏览 25447人参与

# 薪资一样，你会选择去大厂还是小公司 #

16776次浏览 103人参与

# 辞职之后最想做的一件事 #

11490次浏览 167人参与

# 你见过最离谱的招聘要求是什么？ #

188702次浏览 1404人参与

# 选offer应该考虑哪些因素 #

20718次浏览 302人参与

# 金蝶求职进展汇总 #

44154次浏览 242人参与

# 晒一晒你收到的礼盒 #

62794次浏览 376人参与

# 非技术岗薪资爆料 #

355874次浏览 2747人参与

# Offer比较，求稳定还是求发展 #

49637次浏览 240人参与

# 你怀疑过自己的专业选择吗？ #

17593次浏览 201人参与

# 为了秋招你都做了哪些准备？ #

11120次浏览 166人参与

# 你想吐槽公司的哪些规定 #

17817次浏览 68人参与

# 工作中的卑微时刻 #

9146次浏览 56人参与

# 第一份工作应该只看薪资吗 #

139049次浏览 1462人参与

# 我的工作日记 #

98932次浏览 1274人参与

# 秋招想进国企该如何准备 #

58525次浏览 376人参与

牛客网
牛客企业服务