分段打表技巧

什么是打表

打表，也叫硬编码，也就是说对问题进行预计算，把结果作为一张常量表写进代码，并在后续求解中使用它，通常是为了降低时间复杂度。

为什么要打表

在力扣的评论区，往往有这样的身影，让你点开评论时能卡上半天。定睛一看，竟然是偷出了所有的测试用例，作为一张哈希表，来实现AC。在被一道困难题困扰时，或许这样的行为会让你忍俊不禁，缓解一下情绪。

这样的打表，基本上有三种可能。

第一种是题目超出能力范围，算法根本没学过，求不出答案，那就得利用每次错误返回的用例和答案来打表，错了无数次，就可以偷出所有样例了，打表返回便能通过。

第二种是能求出答案，然而不是最优算法，提交时会超出时间限制，由于本地没有限制，可以在本地先跑完，然后把TLE的样例单独打表。由于极端数据不多，需要打的表也不多。这是最方便的自欺欺人的手段😂。

以上两种都是耍小聪明了，因为一旦添加测试用例，错误和低效就无处遁形了（这也是硬编码的缺陷，就是不可扩充性）。所以在周赛中，即使打表通过，赛后的rejudge也过不了。

然而，还有第三种情况，那就是，由于算法能力有限，能力被限定在一定范围内，如果这个范围很小，那就完全可以预计算出来，然后打表返回，并且也没有rejudge空间（比如经典的N皇后问题），这样的打表是相对安全的。

数据范围很大，还能打表吗？

考虑这样一个问题：给定正整数N，要我们计算1~N的阶乘和，也就是1!+2!+3!+...+N!，并对1e9+7取模返回，其中1<=N<=2e8，时间限制1s，阶乘和问题，大概是每个语言都有的循环联系题，是用来训练基本语法的。很自然地，可以写出如下代码，时间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main()
{
    long long n, ans = 0, mod = 1000000007, now = 1;
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
    {
        now = (now % mod) * (i % mod);
        ans = (ans + now) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

然而，这样一个O(N)的代码，在计算N=2e8时，我本地也用了5.68秒，也就是说，数字极大时，不满足时间要求。

可是，还能怎样优化呢？恐怕没有什么空间了吧。然而，我们可以用打表的方法，来“缩减“数据范围。这就是分段打表的技巧。

分段打表

在本地测试时，发现计算N=1e7时，用时仅有0.34秒，这是满足1s内的要求的。有没有一种方法，可以将2e8的范围缩到1e7？

我们有这样的思路：

观察上面的代码，可以知道，对于每一个输入，我们都是从1开始，一直计算到N，在过程中，我们可以给出1~N所有数的答案。然而，如果要打一张2e8的表，太不现实，要么代码长度超限，要么内存超限。

同时，我们也注意到，10和2e8，我们都从1开始搜索，是不是太浪费了呢？如果我们可以每一段选定一个搜索起点，保存起点的状态，然后根据这个数在哪一段，就从哪一段开始搜索，不就减少了很多搜索范围嘛！

所以，我们采用分段打表的方法，将0,1e7,2e7,3e7,...19e7,20e7的结果都保存下来，然后先确定位置，然后从那里开始搜索。这样，最多，也只需要搜索1e7的空间，是完全可以接受的。

而每个点的状态，就是一个ans，一个now，我们打两张长度为21的表就行了（具体打表过程可以一个一个手算，也可以在运算中输出，就不详述了）。

可以得到如下的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main()
{
    long long n, ans = 0, mod = 1000000007, now = 1;
    long long memo1[21] = {0,         506743317, 855672749, 291890662, 659553899, 267849948, 491604009,
                           870446692, 856596552, 48398924,  389768174, 267529910, 424757725, 23766750,
                           839150749, 621426485, 344928972, 184293648, 310371286, 43187357,  9949683},
              memo2[21] = {1,2500153700000000,15556956600000000,1931436090000000,5169088760000000,
                           33236021300000000,13233099120000000,56350797020000000,5730156240000000,
                           33135612120000000,38874219200000000,69733818770000000,65539290120000000,
                           32352234850000000,89992068600000000,34087975500000000,34873001440000000,
                           76227962600000000,61762024980000000,38594491380000000,180964911200000000};
    scanf("%lld", &n);
    ans = memo1[n / 10000000];
    now = memo2[n / 10000000];
    for (int i = (n / 10000000) * 10000000 + 1; i <= n; ++i)
    {
        now = (now % mod) * (i % mod);
        ans = (ans + now) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

在OJ上提交结果是64ms，看来数据造的是比较接近起点的。

分段打表的适用题目

分段打表特别适用于具有大量重复搜索过程的题目。有点像是动态规划，只不过我们是人为地储存了一些状态，并从这些状态开始展开搜索。下面再举一个我在周赛中曾遇到的题目。leetcode2376. 统计特殊整数，题目如下：

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

 

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

 

提示：

  • 1 <= n <= 2 * 109

观察范围，本题达到了2e9的范围，O(N)是显然会超时的，我们考虑用分段打表来进行优化。比较朴素的方法是同样每1e7打表，不过还得利用位运算来优化一下(1600ms)，如果用数组来存，也会超时。。。所以还可以选择1e6打表(这就需要打一张2001的表，不过也可以接受)，这样的话，可以将时间压到250ms左右。下面的代码是1e7打表的结果

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
39
40
41
static int memo[201] = {
            0,       712890,  894330,  1075770, 1257210, 1438650, 1620090, 1801530, 1982970, 2164410, 2345850, 2386170,
            2386170, 2426490, 2466810, 2507130, 2547450, 2587770, 2628090, 2668410, 2708730, 2749050, 2789370, 2789370,
            2829690, 2870010, 2910330, 2950650, 2990970, 3031290, 3071610, 3111930, 3152250, 3192570, 3192570, 3232890,
            3273210, 3313530, 3353850, 3394170, 3434490, 3474810, 3515130, 3555450, 3595770, 3595770, 3636090, 3676410,
            3716730, 3757050, 3797370, 3837690, 3878010, 3918330, 3958650, 3998970, 3998970, 4039290, 4079610, 4119930,
            4160250, 4200570, 4240890, 4281210, 4321530, 4361850, 4402170, 4402170, 4442490, 4482810, 4523130, 4563450,
            4603770, 4644090, 4684410, 4724730, 4765050, 4805370, 4805370, 4845690, 4886010, 4926330, 4966650, 5006970,
            5047290, 5087610, 5127930, 5168250, 5208570, 5208570, 5248890, 5289210, 5329530, 5369850, 5410170, 5450490,
            5490810, 5531130, 5571450, 5611770, 5611770, 5611770, 5611770, 5616810, 5621850, 5626890, 5631930, 5636970,
            5642010, 5647050, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
            5652090, 5657130, 5657130, 5657130, 5662170, 5667210, 5672250, 5677290, 5682330, 5687370, 5692410, 5697450,
            5697450, 5702490, 5702490, 5707530, 5712570, 5717610, 5722650, 5727690, 5732730, 5737770, 5737770, 5742810,
            5747850, 5747850, 5752890, 5757930, 5762970, 5768010, 5773050, 5778090, 5778090, 5783130, 5788170, 5793210,
            5793210, 5798250, 5803290, 5808330, 5813370, 5818410, 5818410, 5823450, 5828490, 5833530, 5838570, 5838570,
            5843610, 5848650, 5853690, 5858730, 5858730, 5863770, 5868810, 5873850, 5878890, 5883930, 5883930, 5888970,
            5894010, 5899050, 5899050, 5904090, 5909130, 5914170, 5919210, 5924250, 5929290, 5929290, 5934330, 5939370,
            5939370, 5944410, 5949450, 5954490, 5959530, 5964570, 5969610, 5974650, 5974650};
class Solution {
public:
    int countSpecialNumbers(int n) {
        int ans=memo[n/10000000];
        for(int i=(n/10000000)*10000000+1;i<=n;++i)
        {
            int copy=i,flag=true;
            long long a=1<<11;
            while(copy)
            {
                if(a&(1<<copy%10))
                {
                    flag=false;
                    break;
                }
                a^=1<<copy%10;
                copy/=10;
            }
            ans+=flag;
        }
        return ans;
    }
};

另一种方法是用打表来辅助dfs，这需要一些前置知识：位数为k的各位不相同的数字有多少个？这可以用排列组合的方法求得，具体可以看leetcode357. 统计各位数字都不同的数字个数。然后，我们可以继续求得1~k位的各位不相同的数字有多少个，只需要求一个前缀和。然后，在此基础上展开dfs即可，这就只需要求位数相同且小于等于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
//考虑问题的规模：一共只有10个数字可选，在保证不重复的情况下，再怎么排列，也只有sigma_{i=1}^10(A 10 i)=9864100种
//1*10^7的规模，还是可以接受的，所以可以大胆遍历
//实际上，比它少一位的所有数可以用357的方法，或者直接打表返回，只需要搜索位数相同的数即可
int memo[11]={0,9,90,738,5274,32490,168570,712890,2345850,5611770,8877690};
class Solution {
public:
    long ans=0,now=0,cnt;//cnt为位数-1
    bool used[10]={0};//判断数字是否用过的数组
    void search(int n)//搜索所有位数相同且较小的数
    {
        if(now!=0&&(int)log10(now)==cnt)//位数相同，找到了一个数
            ++ans;
        else
        {
            int bound=(int)(n/pow(10,cnt-(now==0?-1:(int)log10(now))-1));//前几位的上界
            for(int i=0;i<10&&now*10+i<=bound;++i)
                if((now||i)&&used[i]==0)
                {
                    now=now*10+i;
                    used[i]=true;
                    search(n);
                    now/=10;
                    used[i]=false;
                }
        }
    }   
    int countSpecialNumbers(int n) {
        ans=memo[cnt=log10(n)];//获取比n小一位的所有特殊数
        search(n);
        return ans;
    }
};

一些反思

需要指出的是，分段打表一般都不是正解，比如上面那题，正解就是数位DP。不过，它是比较保险的得分手段，在打表时，要在时间和空间上找到一个均衡，其他也没什么注意点了。

如果有能力，还是应该学习一下正解，因为如果题目想要卡人，可以使打表变得很困难，比如902. 最大为 N 的数字组合 - 力扣（LeetCode）。由于数字组合不定，仍然采取原来的写法，需要打9!=362880张表，先不提代码量的问题，从打表时间消耗来看，假设1s打一张表，也需要100多小时，这是不可想象的，而这题的数位dp写法却并不麻烦，可以研究一下。

可以用分段打表解决的数位DP题目

233. 数字 1 的个数 - 力扣（LeetCode）

面试题 17.06. 2出现的次数 - 力扣（LeetCode）

600. 不含连续1的非负整数 - 力扣（LeetCode）

902. 最大为 N 的数字组合 - 力扣（LeetCode）

1012. 至少有 1 位重复的数字 - 力扣（LeetCode）