hiho一下第146周《子矩阵求和》题目分析

20
8

我们设Sij表示左上角是Aij的子矩阵的和。

那么有两个重要的性质:

  1. Sij + N × M = Si+1,j+1
  2. 当y>=N时,S1,y=S1,y+1。当x>=M时,Sx,1=Sx+1,1。

根据性质1,我们只要知道S11的值,那么S11,S22,S33...这条对角线上的子矩阵和哪些是K的倍数,只要解一个同余方程S11+xNM=0 mod K。这个方程可以先用O(K)的预处理求出xNM=0 ... K- 1 mod K的解,每次求S11+xNM=0 mod K的解是查表即可。另外也可以用扩展欧几里得的方法直接求解。

同理知道S12可以得到S23,S34,S45...

根据性质2,我们只要求S11,S12,S13...S1N和S21,S31,S41...SM1这O(N+M)条对角线上哪些子矩阵是K的倍数就行。

最后每个子矩阵求和可以O(1)得出(找规律用数学方法求和)。

总的时间复杂度是O(N+M)。

  • 请问这道题的数组大小该怎么设置

  • 这个题的样例用欧几里得扩展法能过么?

  • 应该是y>=max(N,M)时,S1,y=S1,y+1吧

  • 添加评论
  • reply

0 answer(s)

write answer 切换为英文 切换为中文


转发分享