DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Swap and Matrix Multiplication

返回题目

题解

연산 전의 값을 S0S_0S0​이라 하자. Ax,k=aA_{x,k}=aAx,k​=a와 Bk,x=bB_{k,x}=bBk,x​=b를 교환하고 d=b−ad=b-ad=b−a라 하자. 교환 후 Ax,kA_{x,k}Ax,k​는 ddd만큼 증가하고 Bk,xB_{k,x}Bk,x​는 ddd만큼 감소한다.

SSS에 포함된 원소 중 xxx번째 행에서 대각선 오른쪽에 있는 원소의 변화량 합은

d∑j=x+1NBk,jd\sum_{j=x+1}^{N}B_{k,j}dj=x+1∑N​Bk,j​

이고, xxx번째 열에서 대각선 위쪽에 있는 원소의 변화량 합은

−d∑i=1x−1Ai,k-d\sum_{i=1}^{x-1}A_{i,k}−di=1∑x−1​Ai,k​

이다. 대각 원소에서는 Ax,kBk,x=abA_{x,k}B_{k,x}=abAx,k​Bk,x​=ab가 교환 후에도 ba=abba=ab이므로 변화량이 이다. 따라서 전체 변화량은

Δx,k=(Bk,x−Ax,k)(∑j=x+1NBk,j−∑i=1x−1Ai,k)\Delta_{x,k}=(B_{k,x}-A_{x,k})\left(\sum_{j=x+1}^{N}B_{k,j}-\sum_{i=1}^{x-1}A_{i,k}\right)Δx,k​=(B

이다.

AAA의 열별 앞쪽 누적합과 BBB의 행별 뒤쪽 누적합을 다음과 같이 정의한다.

Pi,k=∑r=1iAr,k,Qk,i=∑c=iNBk,cP_{i,k}=\sum_{r=1}^{i}A_{r,k},\qquad Q_{k,i}=\sum_{c=i}^{N}B_{k,c}Pi,k​=r=1

P0,k=0P_{0,k}=0P0,k​=0, Qk,N+1=0Q_{k,N+1}=0Qk,N+1​으로 두면 각 변화량은

Δx,k=(Bk,x−Ax,k)(Qk,x+1−Px−1,k)\Delta_{x,k}=(B_{k,x}-A_{x,k})(Q_{k,x+1}-P_{x-1,k})Δx,k​=(Bk,

로 O(1)O(1)O(1)에 계산할 수 있다.

초기 합도 행렬곱 전체를 만들 필요 없이 합의 순서를 바꾸어 계산한다.

S0=∑i=1N∑k=1NAi,kQk,iS_0=\sum_{i=1}^{N}\sum_{k=1}^{N}A_{i,k}Q_{k,i}S0​=i=1∑N​

연산을 하지 않는 경우를 포함해야 하므로 정답은

S0+max⁡(0,max⁡1≤x,k≤NΔx,k)S_0+\max\left(0,\max_{1\leq x,k\leq N}\Delta_{x,k}\right)S0​+max(0,1≤x,k≤N

이다. 시간 복잡도와 공간 복잡도는 모두 O(N2)O(N^2)O(N2)이다.

Solution written by GPT6

ba
=
ab
000
k,x
​
−
Ax,k​)(j=x+1∑N​Bk,j​−i=1∑x−1​Ai,k​)
∑
i
​
Ar,k​
,
Qk,i​
=
c=i∑N​Bk,c​
=
0
x
​
−
Ax,k​)(Qk,x+1​−
Px−1,k​)
k=1∑N​
Ai,k​
Qk,i​
max
​
Δx,k​
)