ACdream 1139 Sum：公式推導 + 模逆元求矩陣路徑和

題目

n×n 數字矩陣 (0-9)。每行相鄰數字組成的數（如 123 產生 1,2,3,12,23,123），每列同理。求所有這些數的和模 1e9+7。n ≤ 1000。

數學推導

考慮位置 (x,y) 的數字 d = a[x][y]。
行貢獻：d 作為第 k 位（從右起）出現的次數 = x * (10^{n-y} + 10^{n-y-1} + ... + 10^0) = x * (10^{n-y+1}-1)/9。
列貢獻同理：y * (10^{n-x+1}-1)/9。
總和 = Σ_{i=1}^n i * (rowSum[i] + colSum[i]) * (10^{n-i+1}-1)/9。
其中 rowSum[i] = 第 i 行數字和，colSum[i] = 第 i 列數字和。
等比數列求和分母 9 需模逆元：inv9 = 9^{MOD-2} mod MOD。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long mod_pow(long long a, long long e) {
    long long r=1; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; } return r;
}
int main() {
    int n; while(scanf("%d",&n)==1) {
        vector g(n);
        for(int i=0;i>g[i];
        vector sum(n+1,0);
        for(int i=0;i