CF414B Mashmokh and ACM

题目描述

Mashmokh's boss, Bimokh, didn't like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh's team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn't able to solve them. That's why he asked you to help him with these tasks. One of these tasks is the following.

A sequence of ll integers $b_{1},b_{2},...,b_{l}(1<=b_{1}<=b_{2}<=...<=b_{l}<=n)$ is called good if each number divides (without a remainder) by the next number in the sequence. More formally $b_i | b_{i+1}$ for all $i (1<=i<=l-1)(1<=i<=l−1)$ .

Given $n$ and $k$ find the number of good sequences of length $k$ . As the answer can be rather large print it modulo $1000000007 (10^9+7)$ .

输入格式

The first line of input contains two space-separated integers $n,k (1<=n,k<=2000)$ .

输出格式

Output a single integer — the number of good sequences of length $k$ modulo $1000000007(10^{9}+7)$ .

题意翻译

如果一个数列中，后一个数都能被前面一个数整除，那么就叫这个数列为好数列。输入n，k，求数列中最大元素为n，数列长度为k的好数列的种数（对1000000007取模）
由 @ROBOT233 提供翻译

输入输出样例

输入： 3 2 输出：5
输入： 6 4 输出：39
输入： 2 1 输出：2

说明/提示
In the first sample the good sequences are:

[1,1],[2,2],[3,3],[1,2],[1,3][1,1],[2,2],[3,3],[1,2],[1,3]

基本思路

使用动态规划，定义dp[k][i]表示1～i的序列中，以i结尾并且长度为k的好数列的种数，那么dp[k][i]与以j结尾（j<=i)且长度为k-1的好数列种数有关，即dp[k-1][i]，好数列的条件既要求i%j==0.

for (int j = i; j > 0; --j)
    if (i % j == 0) dp[k][i] = (dp[k][i] + dp[k - 1][j]) % MOD;

状态转移图

//超时TLE
#include<iostream>

#define MOD 1000000007
#define ll long long
using namespace std;

ll dp[2001][2001];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) dp[1][i] = 1;

    ll ans = 0;
    for (int t = 2; t <= k; ++t)
        for (int i = 1; i <= n; ++i)
            for (int j = i; j > 0; --j)
                if (i % j == 0)
                    dp[t][i] = (dp[t][i] + dp[t - 1][j]) % MOD;
                
    for (int i = 1; i <= n; ++i) ans = (ans + dp[k][i]) % MOD;
    for (int t = 1; t <= k; ++t) {
        cout << t << ": ";
        for (int i = 1; i <= n; ++i)
            cout << dp[t][i] << ' ';
        cout << '\n';
    }
    cout << ans << '\n';

}

python3版本，超时

def solve():
    MOD = 1000000007
    n, k = list(map(int, input().strip().split(' ')))
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    for i in range(1, n + 1):
        dp[1][i] = 1

    for t in range(2, k + 1):
        for i in range(1, n + 1):
            for j in range(i, 0, -1):
                if i % j == 0:
                    dp[t][i] = (dp[t][i] + dp[t - 1][j]) % MOD

    ans = sum(dp[k]) % MOD
    print(ans)

    for row in dp:
        print(row)


if __name__ == '__main__':
    solve()

可以发现，因为当前数应是前一个数的倍数，因为 j 循环可以使用倍数 来减少循环。

#include<iostream>

#define MOD 1000000007
#define ll long long
using namespace std;

ll dp[2001][2001];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) dp[1][i] = 1;

    ll ans = 0;
    for (int t = 2; t <= k; ++t) 
        for (int j = 1; j <= n; ++j) 
            for (int i = 1; i * j <= n; ++i) 
                dp[t][i * j] = (dp[t][i * j] + dp[t - 1][j]) % MOD;

    for (int i = 1; i <= n; ++i) ans = (ans + dp[k][i]) % MOD;

    for (int t = 1; t <= k; ++t) {
        cout << t << ": ";
        for (int i = 1; i <= n; ++i)
            cout << dp[t][i] << ' ';
        cout << '\n';
    }

    cout << ans << '\n';
}

#遗憾的是，python3版本仍然超时
def solve():
    MOD = 1000000007
    n, k = list(map(int, input().strip().split(' ')))
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    for i in range(1, n + 1):
        dp[1][i] = 1

    for t in range(2, k + 1):
        for j in range(1, n + 1):
            for i in [i * j for i in range(1, n + 1) if i * j <= n]:
                dp[t][i] = (dp[t][i] + dp[t - 1][j]) % MOD

    ans = sum(dp[k]) % MOD
    print(ans)

    for row in dp:
        print(row)


if __name__ == '__main__':
    solve()

测试

输入：6 4
输出：
1: 1 1 1 1 1 1 
2: 1 2 2 3 2 4 
3: 1 3 3 6 3 9 
4: 1 4 4 10 4 16 
39

节约内存

由于动态规划过程中，只利用了二维矩阵某一行上的信息，即长度为 $k$ 的好数列仅仅与长度为 $k-1$ 的好数列有关，尝试将二维矩阵压缩成一维。

#include<iostream>

#define MOD 1000000007
#define ll long long
using namespace std;

ll dp[2001] = {0};
ll pre[2001] = {0};

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) pre[i] = 1;

    ll ans = 0;
    for (int t = 2; t <= k; ++t) {
        for (int j = 1; j <= n; ++j) {
            for (int i = 1; i * j <= n; ++i) {
                dp[i * j] = (dp[i * j] + pre[j]) % MOD;
            }
        }
        for (int j = 1; j <= n; ++j) {
            pre[j] = dp[j];
            dp[j] = 0;
        }
    }

    for (int i = 1; i <= n; ++i) ans = (ans + pre[i]) % MOD;

    for (int i = 1; i <= n; ++i)
        cout << pre[i] << ' ';
    cout << '\n';

    cout << ans << '\n';
}

还可以进一步减少内存

#include<iostream>

#define MOD 1000000007
#define ll long long
using namespace std;

ll dp[2001] = {0};

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) dp[i] = 1;

    ll ans = 0;
    for (int t = 2; t <= k; ++t) 
        for (int j = n; j > 0; --j) 
            for (int i = 2; i*j <= n; ++i) 
                dp[i * j] = (dp[i * j] + dp[j]) % MOD;

    for (int i = 1; i <= n; ++i) ans = (ans + dp[i]) % MOD;

    for (int i = 1; i <= n; ++i)
        cout << dp[i] << ' ';
    cout << '\n';

    cout << ans << '\n';
}