自动搬运

查看原文

来自洛谷，原作者为

	tuxiaolai 国家特级保护废物一只||终于上估值排行榜了！

搬运于2025-08-24 22:08:47，当前版本为作者最后更新于2025-07-31 10:24:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

1 说明

本题解思路与楼上题解完全相同，但会详细讲解。

前置芝士：矩阵乘法。

2 审题

题目定义说人话就是：

$G(N)$ 表示 $N$ 的各位数字之和。
$S_N$ 为所有符合 $G(x) \le N$ 的正整数 $x$ 所构成的集合。
$F(N)$ 为集合 $S_N$ 中所有元素两两相乘再求和后的结果。

（为与下文区分，这里将 $f$ 和 $g$ 改为大写）

3 思路

3.1 原式变形

我们假设 $S_N$ 中的元素为 $x_{1\sim n}$。
将原式变形可得：

$$F(N)=\sum_{1 \leq i < j \leq n} x_i \times x_j$$

由恒等式：

$$\left( \sum_{i=1}^{n} x_i \right)^2 = \sum_{i=1}^{n} x_i^2 + 2 \times \sum_{1 \leq i < j \leq n} x_i \times x_j $$

可得：

$$F(N)=\frac{\left( \sum x \right)^2-\sum x^2}{2}$$

3.2 动态规划

很多矩阵运算的题都可以先考虑：假如数据不大，可以怎样用动态规划来解决。

楼上的思路非常巧妙：首先，我们定义：
$f_i$ 为 $G(x)=i$ 的 $x$ 的个数。
$g_i$ 为 $G(x)=i$ 的 $x$ 的和。
$h_i$ 为 $G(x)=i$ 的 $x$ 的平方和。

下面考虑如何转移 $f,g,h$：

3.2.1 $f$ 的转移

对于 $f_i$，我们先只考虑个位，它可以取 $1 \sim 9$。不难得出：

$$f_i=\sum_{j=1}^{9} f_{i-j}$$

这里注意：我们定义 $f_0=1$，后文会再次讲到。

3.2.2 $g$ 的转移

同样的方式，对于个位的每一种可能 $j$，它除个位外的和是 $g_{i-j} \times 10$，除个位外的方式有 $f_{i-j}$ 种。每种方式都要加上一个 $j$。因此：

$$g_i=\sum_{j=1}^{9} \left( g_{i-j} \times 10 + f_{i-j} \times j \right) $$

3.2.3 $h$ 的转移

对于个位的每一种可能 $j$，我们可以将 $x$ 写作 $10 \times n + j$。那么 $x^2=100 \times n^2 + 20 \times n \times j + j^2$，用上文相同的方法，不难得出：

$$h_i=\sum_{j=1}^9 \left( 100 \times h_{i-j} + 20 \times j \times g_{i-j} + j^2 \times f_{i-j} \right) $$

最后，整道题的答案就是：

$$F(n)=\frac{\left( \sum_{i=1}^{n} g_i \right)^2 - \sum_{i=1}^{n} h_i}{2} $$

3.3 矩阵转移（算法）

首先，我们定一个初始矩阵，共 1 列、29 行：

$$\begin{bmatrix} f_{i-1}\\ f_{i-2}\\ ...\\ f_{i-9}\\ g_{i-1}\\ g_{i-2}\\ ...\\ g_{i-9}\\ h_{i-1}\\ h_{i-2}\\ ...\\ h_{i-9}\\ \sum g\\ \sum h\\ \end{bmatrix} $$

最终预期的结果是：

$$\begin{bmatrix} f_{i}\\ f_{i-1}\\ ...\\ f_{i-8}\\ g_{i}\\ g_{i-1}\\ ...\\ g_{i-8}\\ h_{i}\\ h_{i-1}\\ ...\\ h_{i-8}\\ \sum g\\ \sum h\\ \end{bmatrix} $$

接下来就是用于转移矩阵了（29 列，29 行）：
首先考虑 $f_{i-j},g_{i-j},h_{i-j}(1 \le j \le 8)$ 的转移方式，它们由 $f_{i-j-1},g_{i-j-1},h_{i-j-1}$ 直接转移而来，也就是说：在第 $i$ 行中，第 $i-1$ 列为 1，其他都为 0。（$2 \le i \le 9 \text{ 或 } 11 \le i \le 18 \text{ 或 } 20 \le i \le 27$）

for(int i=1; i<=9; i++) {
    if(i!=9) {
        b.a[i][i+1]=1;//f[i-j]
        b.a[i+9][i+10]=1;//g[i-j]
        b.a[i+18][i+19]=1;//h[i-j]
    }
}

其次就是 $f_i,g_i,h_i$ 的转移：

1. 由 $f_i=\sum_{j=1}^{9} f_{i-j}$，我们可以将第 1 行的第 $i(i \in [1,9])$ 列标为 1，即可实现转移。
2. 由 $g_i=\sum_{j=1}^{9} \left( g_{i-j} \times 10 + f_{i-j} \times j \right)$，我们先将第 10 行的第 $i(i \in [10,18])$ 列标为 10，再将第 $i(i \in [1,9])$ 列分别标为 $i$，即可实现转移。
3. $h_i=\sum_{j=1}^9 \left( 100 \times h_{i-j} + 20 \times j \times g_{i-j} + j^2 \times f_{i-j} \right) $，我们先将第 19 行的第 $i(i \in [19,27])$ 列标为 100，再将第 $i(i \in [10,18])$ 列分别标为 $20 \times (i-9)$，最后将第 $i(i \in [1,9])$ 列分别标为 $i^2$，即可实现转移。

for(int i=1; i<=9; i++) {
    b.a[i][1]=1;//f[i]

    b.a[i][10]=i;//g[i]
    b.a[i+9][10]=10;

    b.a[i][19]=i*i;//h[i]
    b.a[i+9][19]=20*i;
    b.a[i+18][19]=100;
}

最后是 $\sum g,\sum h$ 的转移，直接在 $g_i,h_i$ 的转移方式的初始上再加上自己，就可以实现增加的效果了。

for(int i=1; i<=9; i++) {
    b.a[i][28]=i;//sum g
    b.a[i+9][28]=10;

    b.a[i][29]=i*i;//sum h
    b.a[i+9][29]=20*i;
    b.a[i+18][29]=100;
}
b.a[28][28]=1;//sum g
b.a[29][29]=1;//sum h

那么最后的最后，我们将初始矩阵初始化：直接让第 1 行的数字为 1 即可，（前面说到定义 $f_0=1$，这样既不会影响 $f$ 的转移，反而还能让 $g,h$ 的转移正确大家可以仔细想想）。
不过这时我们仔细观察转移矩阵，由于结果只取决于第 1 列，我们会发现转移矩阵 1 列与初始矩阵乘上一个转移矩阵后的结果恰好相同，这就意味着我们可以不乘初始矩阵，直接用转移矩阵的 $n$ 次方作为答案即可。

4 AC CODE

#include <bits/stdc++.h>
using namespace std;
const int mod=1e6+3;
struct Mat {
    long long a[30][30];
    Mat operator*(const Mat &other)const {
        Mat res;
        for(int i=1; i<=29; i++) {
            for(int j=1; j<=29; j++) {
                res.a[i][j]=0;
                for(int k=1; k<=29; k++) {
                    res.a[i][j]+=a[i][k]*other.a[k][j];
                    res.a[i][j]%=mod;
                }
            }
        }
        return res;
    }
    void init() {
        for(int i=1; i<=29; i++) {
            for(int j=1; j<=29; j++) {
                a[i][j]=0;
            }
        }
        return;
    }
};
Mat fpow(Mat b,long long c) {
    Mat res=b;
    c--;
    while(c) {
        if(c&1) {
            res=res*b;
        }
        b=b*b;
        c>>=1;
    }
    return res;
}
int inv(int a,int b) {
    int res=1;
    b-=2;
    while(b) {
        if(b&1) {
            res=(long long)res*a%mod;
        }
        a=(long long)a*a%mod;
        b>>=1;
    }
    return res;
}
long long n;
Mat b;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    b.init();
    for(int i=1; i<=9; i++) {
        b.a[i][1]=1;//f[i]

        b.a[i][10]=i;//g[i]
        b.a[i+9][10]=10;

        b.a[i][19]=i*i;//h[i]
        b.a[i+9][19]=20*i;
        b.a[i+18][19]=100;

        b.a[i][28]=i;//sum g
        b.a[i+9][28]=10;

        b.a[i][29]=i*i;//sum h
        b.a[i+9][29]=20*i;
        b.a[i+18][29]=100;
        if(i!=9) {
            b.a[i][i+1]=1;//f[i-j]
            b.a[i+9][i+10]=1;//g[i-j]
            b.a[i+18][i+19]=1;//h[i-j]
        }
    }
    b.a[28][28]=1;//sum g
    b.a[29][29]=1;//sum h
    cin>>n;
    Mat ans=fpow(b,n);
    cout<<(ans.a[1][28]*ans.a[1][28]-ans.a[1][29])%mod*inv(2,mod)%mod;
    return 0;
}

5 其他

1. 上文中的转移矩阵。
2. 时间似乎还能优化一点，请各位大佬指出。
3. 由于内容较多，若有笔误请及时提出。