小易喜欢的数列

题目：
小易非常喜欢拥有以下性质的数列:
1、数列的长度为n
2、数列中的每个数都在1到k之间(包括1和k)
3、对于位置相邻的两个数A和B(A在B前),都满足(A <= B)或(A mod B != 0)(满足其一即可)
例如,当n = 4, k = 7
那么{1,7,7,2},它的长度是4,所有数字也在1到7范围内,并且满足第三条性质,所以小易是喜欢这个数列的但是小易不喜欢{4,4,4,2}这个数列。小易给出n和k,希望你能帮他求出有多少个是他会喜欢的数列。

输入描述:

输入包括两个整数n和k(1 ≤ n ≤ 10, 1 ≤ k ≤ 10^5)

输出描述:

输出一个整数,即满足要求的数列个数,因为答案可能很大,输出对1,000,000,007取模的结果。

示例1

输入

2 2

输出

3

思路：

若n = 4 , k = 7

• 方法一：

第i位	第i+1位可选值
1	1 2 3 4 5 6 7
2	2 3 4 5 6 7
3	2 3 4 5 6 7
4	3 4 5 6 7
5	2 3 4 5 6 7
6	4 5 6 7
7	2 3 4 5 6 7

由上表可以，当前位的值将决定下一位值的范围，因此，自然而然可以递归去求解。也就是动态规划的方法：当前位确定数值后，余下位共有多少种情况。详见下面代码中的func1函数。

• 方法二：
  递归方法的最底层返回定值，那么从定值出发向后反推各层数值，就可以将递归转换为循环进而提高效率。
  第4位为某值的情况已知，那么当第3位为某值时共有多少情况可由第4位对应的值累加，逐位向前即可得到总共有1201=220+190+180+147+180+114+180种情况。

数字	第4位	第3位	第2位	第1位
1	1	7 (第4位可取1 2 3 4 5 6 7)	40=(7+6+6+5+6+4+6)	220
2	1	6 (第4位可取2 3 4 5 6 7)	33=(6+6+5+6+4+6)	180
3	1	6 (第4位可取2 3 4 5 6 7)	33=(6+6+5+6+4+6)	180
4	1	5 (第4位可取3 4 5 6 7)	27=(6+5+6+4+6)	147
5	1	6 (第4位可取2 3 4 5 6 7)	33=(6+6+5+6+4+6)	180
6	1	4 (第4位可取4 5 6 7)	21=(5+6+4+6)	114
7	1	6 (第4位可取2 3 4 5 6 7)	33=(6+6+5+6+4+6)	180

为了提高效率，在求解当前位的情况数时，是由前一列之和减去不满足条件的项来得到当前位的值。而从高位到低位的算法，每项的不满足条件项较复杂，计算量大，会有超时的情况，因此，我们使用从低位向高位求解的方法。

如下,
当第2位为1时，第1位需排除{2,3,4,5,6,7}={12, 2+1, 3+1, 4+1, 5+1, 6+1}
当第2位为2时，第1位需排除{4,6}={22, 4+2}
当第2位为3时，第1位需排除{6}={3*2}
当k比较大时，这种从低位到高位的过程，排除不满足条件的项数非常少，比从高位到低位的计算量小很多。详见下面代码中的func2函数。

数字	第1位	第2位	第3位	第4位
1	1	1 (第1位可取1)	1 (第2位可取1)	1
2	1	5 (第1位可取1 2 3 5 7)	26=(1+5+6+7+7)	140
3	1	6 (第1位可取1 2 3 4 5 7)	33=(1+5+6+7+7+7)	180
4	1	7 (第1位可取1 2 3 4 5 6 7)	40=(1+5+6+7+7+7+7)	220
5	1	7	40	220
6	1	7	40	220
7	1	7	40	220

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

using namespace std;

class Solution {
private:
    int n;
    int k;
    long res1;
    long res2;
    int mod = 1000000007;
    
private:
    void init() {
        cin >> n >> k;
    }
    void write_result() {
        cout << res1 << endl << res2;
    }
    void calculate_result() {
        if (n == 0 || k == 0)
            return;
        res1 = func1(n + 1, 1);
        res2 = func2();
    }
    int func1(int index, int pre_num) {
        int count = 0;
        if (index < 2)
            count = 1;
        else {
            for (int i = 1; i < pre_num; i++)
                if (pre_num%i != 0)
                    count += func1(index - 1, i);
            for (int i = pre_num; i <= k; i++)
                count += func1(index - 1, i);
        }
        return count;
    }
    long func2() {
        vector<long> vt(k + 1, 1);
        long vtsum = k;
        vector<vector<int>> noncdt(k + 1);
        for (int i = 1; i <= k; i++) {
            for (int j = i + i; j <= k; j += i) {
                noncdt[i].push_back(j);
            }
        }
        for (int col = 1; col < n; col++) {
            long newsum = 0;
            for (int row = 1; row <= k; row++) {
                long del = 0;
                for (auto d : noncdt[row]) {
                    del += vt[d];
                    del %= mod;
                }
                vt[row] = (vtsum - del + mod) % mod;
                newsum += vt[row];
                newsum %= mod;
            }
            vtsum = newsum;
        }

        return vtsum;
    }

public:
    void solve() {
        init();
        calculate_result();
        write_result();
    }
};

int main()
{
    Solution s;
    s.solve();

    return 0;
}