Project Euler 706

发表于 更新于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

Project Euler 706

题目

\(3\)-Like Numbers

For a positive integer \(n\), define \(f(n)\) to be the number of non-empty substrings of \(n\) that are divisible by \(3\). For example, the string "\(2573\)" has \(10\) non-empty substrings, three of which represent numbers that are divisible by \(3\), namely \(57, 573\) and \(3\). So \(f(2573) = 3\).

If \(f(n)\) is divisible by \(3\) then we say that \(n\) is \(3\)-like.

Define \(F(d)\) to be how many \(d\) digit numbers are \(3\)-like. For example, \(F(2) = 30\) and \(F(6) = 290898\).

Find \(F(10^5)\). Give your answer modulo \(1\,000\,000\,007\).

解决方案

一个非常直接的动态规划题。

令\(N=10^5.\)考虑到子串的个数，通常我们先将这个数\(d=d_1d_2d_3\dots\)看成一个字符串，然后令其前缀和数组为\(s\)，其中\(s[0]=0,s[i]=s[i-1]+d_i\)，那么一个数的子串和就可以通过数组\(s\)进行一次减法求得。

令\(N=10^5\)，假设已有状态\(f(i,c_1,c_2,k,t)(1\le i\le N,0\le c_1,c_2,t<3)\)为有多少个\(i\)位数满足以下条件：

  • 令\(c_0=(i+1-c_1-c_2)\%3\)。这两个值其实也是状态之一，只不过可以被\(i,c_1,c_2\)表出。
  • 目前数组\(s\)一共有\(i+1\)项，其中有\(c_j\)个项模\(3\)的值为\(j(0\le j<3)\) ，注意\(c_j\)已经被\(3\)取模。
  • 目前\(s[i]\)的值为\(k\)。
  • 子串个数和\(t\)关于模\(3\)同余。

那么状态的转移只需要考虑在每个数后面添加一个数位\(0\sim 9\)，注意维护前缀和数组\(s\)新的一项。

本题转移过程考虑进行我为人人式。

不难知道初值\(f(1,0,0,0,1)=f(1,1,0,1,0)=f(1,0,1,2,0)=3\)，这\(3\)种情况分别对应一位数模\(3\)余\(0\)，模\(3\)余\(1\)，模\(3\)余\(2\)的情况。

以\(k=0\)为例，那么有三种方式转移：

\(\begin{aligned} & f(i,c_1,c_2,0,t)\cdot 4\rightarrow f(i+1,c_1,c_2,0,(t+c_0)\%3) \\ & f(i,c_1,c_2,0,t)\cdot 3\rightarrow f(i+1,(c_1+1)\%3,c_2,1,(t+c_1)\%3) \\ & f(i,c_1,c_2,0,t)\cdot 3\rightarrow f(i+1,c_1,(c_2+1)\%3,1,(t+c_2)\%3) \\ \end{aligned}\)

由于目前的前缀和\(s[i]=0\)，那么再添加数位\(0,3,6,9\)中的一个，那么\(s[i+1]=0\)，因此这时就多了\(c_0\)个符合题意的子串；如果添加数位\(1,4,7\)中的一个，那么\(s[i+1]=1\)，因此这时就多了\(c_1\)个符合题意的子串；如果添加一个数位\(2,5,8\)，那么\(s[i+1]=2\)，因此这时就多了\(c_2\)个符合题意的子串。

因此，最终答案为

\[\sum_{c_1=0}^3\sum_{c_2=0}^3\sum_{k=0}^3f(N,c_0,c_1,k,0)\]

本题也可以将整个状态转移过程写成一个\(81\times81\)大小的矩阵，通过矩阵快速幂以\(O(\log N)\)直接计算出结果。此处不再详述这个优化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000;
ll f[N+4][3][3][3][3],mod=1e9+7;
void add(ll &x,ll y){
    x=(x+y)%mod;
}
int main() {
    f[1][0][0][0][1] = 3;
    f[1][1][0][1][0] = 3;
    f[1][0][1][2][0] = 3;
    for (int i = 1; i < N; i++)
        for (int c1 = 0; c1 < 3; c1++)
            for (int c2 = 0; c2 < 3; c2++)
                for (int t = 0; t < 3; t++) {
                    int c0 = (i + 1 - c1 - c2 + 6) % 3;
                    ll &now0 = f[i][c1][c2][0][t], &now1 = f[i][c1][c2][1][t], &now2 = f[i][c1][c2][2][t];
                    add(f[i + 1][c1][c2][0][(t + c0) % 3], now0 * 4); //0,3,6,9
                    add(f[i + 1][(c1 + 1) % 3][c2][1][(t + c1) % 3], now0 * 3);//1,4,7
                    add(f[i + 1][c1][(c2 + 1) % 3][2][(t + c2) % 3], now0 * 3);//2,5,8

                    add(f[i + 1][(c1 + 1) % 3][c2][1][(t + c1) % 3], now1 * 4);//0,3,6,9
                    add(f[i + 1][c1][(c2 + 1) % 3][2][(t + c2) % 3], now1 * 3);// 1,4,7
                    add(f[i + 1][c1][c2][0][(t + c0) % 3], now1 * 3);//2,5,8

                    add(f[i + 1][c1][(c2 + 1) % 3][2][(t + c2) % 3], now2 * 4);//0,3,6,9
                    add(f[i + 1][c1][c2][0][(t + c0) % 3], now2 * 3);//1,4,7
                    add(f[i + 1][(c1 + 1) % 3][c2][1][(t + c1) % 3], now2 * 3);//2,5,8
                }
    ll ans = 0;
    for (int c1 = 0; c1 < 3; c1++)
        for (int c2 = 0; c2 < 3; c2++)
            for (int k = 0; k < 3; k++)
                add(ans, f[N][c1][c2][k][0]);
    printf("%lld\n", ans);
}