贝壳2018.10.15笔试找寻序列

秒速五厘米 2022-05-09 13:38 125阅读 0赞

# 题目描述 #

![在这里插入图片描述][70]  
n确认序列长度，m确定最后一个数。还有一个要求是（从提示可以明显看出），每两个数，后者要能整除前者，比如\[1,3,3\]中，【1,3】要3能整除1，【3,3】要3能整除3。

# 动态规划 #

如果n=1那么只有一种情况。  
如果n>1，那么有递归式，dp\[n,m\] = sum( dp\[n-1\]\[x\] )。x为n所有可能的因数。  
![在这里插入图片描述][70 1]  
根据上图来看，比如找【3,4】，4的因数有1,2,4，那么就等于【2,1】【2,2】【2,4】的个数相加，如果看每个元素存储的序列，那就是【2,1】【2,2】【2,4】里面的各个序列后面再加个4。  
解释一下这个递归式：  
1.第n个数字是m，第n-1个必须是m的因数x  
2.已经确定了第n个数字，剩余的前n-1个数的情况，已经被所有的dp\[n-1\]\[x\]存起来了（因为找的是x，x又是m的因数，所以就可以满足第n-1个是m的因数）  
3.根据这样分析递推，那么又可以得到第n-2个又是第n-1的因数。

#include <bits/stdc++.h>
    using namespace std;
     
    const int mod = 1e9 + 7;
    typedef long long LL;
    LL dp[1005][1005];
     
    int main()
    { 
        for (int i = 1; i < 1005; i++) dp[1][i] = 1;
        for (int i = 2; i < 1005; i++) {       // 长度N
            for (int j = 1; j < 1005; j++) {   // 尾值M
                int tmp = sqrt(j);
                for (int k = 1; k <= tmp; k++) { 
                    if (j % k == 0) { 
                        dp[i][j] += dp[i - 1][k];
                        dp[i][j] %= mod;
                        dp[i][j] += dp[i - 1][j / k];
                        dp[i][j] %= mod;
                    }
                }
                if (tmp * tmp == j) { 
                    dp[i][j] -= dp[i - 1][tmp];
                    dp[i][j] %= mod;
                }
            }
        }
     
        int N, M;
        while (cin >> N >> M) { 
            cout << dp[N][M] << endl;
        }
        return 0;
    }

代码来自牛客网大佬@HanKin，先在此鸣谢。解释一下那个平方根，因为一个数的因数是成对出现的，我们只需要求到1到平方根的因数就行，另一半因数用原数除以因数就能得到。比如10，平方根是3，遍历1,2,3。1是因数，10/1也是因数；2是因数，10/2也是因数。3不是因数。

# 滚动数组 #

修改成py代码，使用滚动数组，降低空间复杂度。

import math
    n,m = map(int,input().split())
    
    mod = 10**9 + 7
    dp = [[0]*(m+1),[1]*(m+1)]
    
    for i in range(2,n+1):
        lastrow = (i-1) % 2
        row = i % 2
        for j in range(1,m+1):
            temp = int(math.sqrt(j))
            dp[row][j] = 0
            for k in range(1,temp+1):
                if j%k == 0:
                    dp[row][j] += dp[lastrow][k]
                    dp[row][j] %= mod
                    dp[row][j] += dp[lastrow][j//k]
                    dp[row][j] %= mod
            if temp*temp == j:
                dp[row][j] -= dp[lastrow][temp]
                dp[row][j] %= mod
    
    print(dp[n%2][m])

可以发现数组是重复利用的，但必须是`[[0]*(m+1),[1]*(m+1)]`，不能只是`[1]*(m+1)`，因为如果这样，算dp\[n,m\] = sum( dp\[n-1\]\[x\] )时，较小的x对应的`dp[n-1][x]`会被更新为`dp[n][x]`，这样等算到较大的x对应的`dp[n][x]`时，需要用到较小的x对应的`dp[n-1][x]`，但此时较小的x对应的`dp[n-1][x]`已经被更新为`dp[n][x]`，这样算出来就不对了。

[70]: /images/20220506/c18a1c1da6324dbebe1ac9c5ecdb9b91.png
[70 1]: /images/20220506/ea1c0a6cd88347a99d4d1271055f3a31.png