题解：P5257 [JSOI2013] 密码
tuxiaolai
·
·
题解
1 说明
本题解思路与楼上题解完全相同，但会详细讲解。
前置芝士：矩阵乘法。
2 审题
题目定义说人话就是：
$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$）
```cpp
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$，即可实现转移。
```cpp
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$ 的转移方式的初始上再加上自己，就可以实现增加的效果了。
```cpp
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
```cpp
#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. 上文中的[转移矩阵](https://www.luogu.me/article/xclsdyz2#)。
2. 时间似乎还能优化一点，请各位大佬指出。
3. 由于内容较多，若有笔误请及时提出。