題意:
給定一個由0~9組成的矩陣,我們求行相鄰的組成的數與列相鄰的組成的數的和。
eg:
123
456
789
第一行組成的數有 1,2,3,12,23,123
第一列組成的數有 1,4,7,12,47,147.
暴力枚舉所有的數肯定是不可取的,我們試著總結。
我們發現a[x][y]在行裡出現的數對以後和的貢獻為 x*a[x][y]sigma(10 ^(n-i)) (k<=x<=n)
同理a[x][y]在列裡出現的數對以後和的貢獻為 y*a[x][y]sigma(10 ^(n-i)) (y<=x<=n)
我們設sum[x]表示第x行與第x列的數的和 然後對以上的公式進行合並
sum = sigma( i * sum[i] * ( sigma(10^k)(i<=k<=n)))(1<=i<=n)
sigma(10^k)(i<=k<=n)用到等比數列求和,有除法,需要用到逆元
a/b (mod c) == a (mod b*c)/c
或者 a*~b (mod c)
代碼如下:
#include
#include
#include
#include
#include
#include
#include