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)$

全部评论

推荐最新楼层

07-22 09:41

钱大妈_应用研发部_前端开发工程师

985学长挂了，双非学妹进了｜校招到底在挑啥人？

家人们！！ 今天必须来聊一个让所有应届生都头大的问题👇  “校招阶段，学历和技术，到底哪个更重要？”  你以为公司只爱985/211？ 错！ 你以为技术牛就能横着走？ 也错！ 真相其实是👇  学历帮你敲门，技术决定你能不能留下来。  🧠【校招真实偏好大揭秘｜HR到底在看啥？】 📌 初筛简历阶段： 👉 学历确实占优势！很多公司用“学校池”自动过滤，双非/普通本科容易被漏掉。 💡但！这只是第一步，不是终点！ 📌 技术面试阶段： 👉 所有人站在同一起跑线！这时候拼的就是：  项目有没有落地？是不是你真做的？ 遇到问题怎么解决？有没有自己的思考？ 技术细节能不能讲清楚？会不会背八股文就...

校招阶段，学历VS技术哪...

点赞评论收藏

分享

07-21 17:56

门头沟学院运营

经历过三段大厂实习后，我发现……

流动性超乎你的想象（我在的几个月，就能经历多个正职离职，有的主动提离职了、有的业务直接砍了……钱比命重要（有些年纪偏大了的同事，生病了也不敢请假怕被优化，整个人都没有光亮了。周末on call 是常态，加班到凌晨也是！！！）汇报比多做更能晋升，会说也是一种能力。说实话，一个项目是一个团队的成果，谁做多做少都很难量化，可能ta只是稍微润色一下就能写成都是ta的结果）不要想着和同事交朋友（尤其是吐槽的话，千万别说，你们是竞争关系，ta随手截图交给mt，你就完了。你们只是上班饭搭子，下班根本不会有任何联系。）看到很多黑色真相，但还是难以对大厂祛魅（福利待遇真的好）秋招还是会拼死卷进去，可能我就是有点...

实习生的蛐蛐区

点赞评论收藏

分享

06-22 21:02

广东药科大学 Java

请问这是在招奴隶吗

这种公司就赶紧避雷吧，有bug半夜也要起来？还学习腾讯，自己几斤几两不清楚吗

Java大菜狗：纯纯招黑奴，一天还不到两百那么多要求，还不迟到早退，以为啥啊，给一点工资做一堆活，还以不拖欠员工工资为荣，这是什么值得骄傲的事情吗，纯纯***公司

点赞评论收藏

分享

06-13 10:15

门头沟学院 Java

这比例对吗，附简历，求锐评

想去夏威夷的大西瓜在...：我也是27届，但是我现在研一下了啥项目都没有呀咋办，哎，简历不知道咋写

点赞评论收藏

分享

07-23 00:26

Momenta26实习

目前虽然26届的实习还在招的只有Mstar了，要求比较高，佬们可以投投给大家详细聊一聊公司上班细节，大家可以评估下自己来了能否适应。智驾整体强度都比较大，因为基本都算初创公司，还没做到能躺着收钱的地步，凡事看两面，压力大但是能学到东西，不至于说每天干重复的东西么没有提示，工作时间10am-19pm，项目交付的时候加班就多，基本上9点左右，公司包三餐 工作再忙都要好好吃饭 公司统一使用美餐app 可以根据自己喜好来订餐到工位餐区也可以去楼下美好荟去合作商家堂食比如：老乡鸡 costa 美餐20元餐标超出部分自己补差价👇 王阿吉的快餐真的很好吃强推 ）别担心会吃腻 行政小姐姐会定期更换合作商家。...

Momenta公司福利 615人发布

点赞评论收藏

分享

评论

4

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 哪些公司开提前批了？ #

25757次浏览 259人参与

# 华子oc时间线 #

1244084次浏览 6483人参与

# 风评不好的公司，你会去吗？ #

60413次浏览 435人参与

# 实习如何「偷」产出？ #

50107次浏览 1314人参与

# 除了主业以外，你还有哪些其他收入？ #

11920次浏览 201人参与

# 不卡学历的大厂有哪些？ #

28522次浏览 224人参与

# 校招阶段，学历VS技术哪个更重要？ #

17322次浏览 186人参与

# 职场新人体验 #

25077次浏览 234人参与

# 哪些公司校招卡第一学历 #

67472次浏览 266人参与

# 腾讯音乐求职进展汇总 #

98087次浏览 570人参与

# 社恐入职新公司如何融入团队 #

11847次浏览 63人参与

# 校园里的破防时刻 #

11128次浏览 125人参与

# Offer比较，你最看重什么？ #

191582次浏览 1301人参与

# 你投递的公司有几家约面了？ #

108901次浏览 779人参与

# 你觉得技术面多长时间合理？ #

100233次浏览 720人参与

# 你最满意的offer薪资是哪家公司？ #

33088次浏览 176人参与

# 你今年的平均薪资是多少？ #

134007次浏览 686人参与

# 你的秋招第一场笔试是哪家 #

147584次浏览 1484人参与

# 正在实习的碎碎念 #

1454689次浏览 13469人参与

# 实习打杂，要跑路吗 #

18056次浏览 202人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务