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

全部评论

推荐最新楼层

11-18 12:10

叮咚买菜_咚力生（管理方向）(准入职员工)

叮咚买菜内推，叮咚买菜内推码

📍 工作地点：在上海市浦东新区叮咚买菜总部，我入职时正好赶上换新办公楼，搬到张江之门啦，新环境新工位，想想就超开心🥳 附近租房价格也比较合理，没有市中心那么夸张。 📝 工作内容：类似采购，但在采购基础上赋予了更大的想象和职能。不再是传统的搬货采购模式，而是要根据消费者需求精准开发产品，全程负责到底。 这边以生鲜为例子：比如帮助一些因各种原因被雪藏的特色生鲜水果走出当地，推广到更多的地方，让消费者尝到美味的特色生鲜水果的同时带动当地的农牧民共同致富💰 例如：大凉山丑苹果，通过以离太阳更近离城市更远，天然无污染为卖点开发出的产品。霜冻菜以抗寒植物在寒冷条件下提升细胞渗透压将淀粉转化为糖的原...

叮咚买菜公司氛围 125人发布

点赞评论收藏

分享

11-20 16:44

西安电子科技大学 Java

为什么面试问的越详细反而没有后文了？

作为一名摸爬滚打了八年的Java开发者，经历了无数次面试与被面试，我观察到一个令人费解的现象：有时面试官问得越深入、越细致，仿佛对你的技术了如指掌，最终却石沉大海，再无回音。 这背后并非偶然，而是不同规模公司对人才需求的底层逻辑差异所致。结合我的亲身经历和思考，我认为核心在于：大厂赌的是你的“潜力”，而中小厂要的是你“立刻能干活”。🧠 大厂视角：深挖是为了验证潜力与深度思考能力在大厂的面试经历中（无论是作为候选人还是面试官），我深刻体会到他们对“问得深”有着不同的目标：“剥洋葱式”提问不是为了刁难，而是考察思维深度： 当面试官不断追问“这个方案为什么最优？”、“如果并发量再增加十倍，瓶颈在哪...

我发现了面试通关密码

点赞评论收藏

分享

10-17 23:18

已编辑

西北农林科技大学 Web前端

还有这种形式的秋招？

这种的会有人参加吗，如果有人参加那我试试

独行m：给25可以试试，但他只能给12，那就是纯纯的事精

秋招，不懂就问

点赞评论收藏

分享

10-30 16:31

重庆大学 Java

27找日常实习

投了3天，沟通160多个，一个面试没有，这正常吗

代码飞升_不回私信人...：你说你善于学习，大家都会说。你说你是985，985会替你表达一切

点赞评论收藏

分享

评论

4

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

199174次浏览 1345人参与

# 材料转码还有必要吗？ #

32028次浏览 152人参与

# 小红书开奖了 #

34518次浏览 167人参与

# 你面试时吹过最大的牛 #

770次浏览 10人参与

# 设计人的面试记录 #

166972次浏览 1545人参与

# 实习学到最有价值的工作习惯 #

41418次浏览 363人参与

# 百度秋招 #

52929次浏览 389人参与

# 蚂蚁求职进展汇总 #

133241次浏览 1210人参与

# 2022毕业即失业取暖地 #

121524次浏览 710人参与

# 你知道哪些职场黑话？ #

64739次浏览 449人参与

# 正在春招的你，也参与了去年秋招吗？ #

335199次浏览 2563人参与

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

25859次浏览 497人参与

# 那些年，我收到的‘奇葩’回复 #

30028次浏览 177人参与

# 实习需要主动找活干吗？ #

56403次浏览 297人参与

# CVTE求职进展汇总 #

26543次浏览 327人参与

# 牛客十周岁生日快乐 #

186121次浏览 1829人参与

# 秋招你经历过哪些无语的事 #

27133次浏览 263人参与

# 双非本科的出路是什么？ #

178920次浏览 1456人参与

# 校招薪资来揭秘 #

98280次浏览 605人参与

# 材料人，你最希望上岸的是？ #

13186次浏览 58人参与

# 科大讯飞工作体验 #

29032次浏览 69人参与

# 你今年的保底offer是哪家 #

145196次浏览 620人参与

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