ZOJ 4011 Happy Sequence dp

传送门：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370222

题意

给一个n和一个m，表示你可以重复用[1,n]里的数字。

构造一个数列，数列中前一个数字必须是后一个数字的因子，即$a_ia_{i+1}$。

问能构造多少个这样的数列。

思路

比如n=8，m=3.可以构造：

$8\;8\;8$ $8\;8\;4$ $8\;4\;4$ $4\;4\;4$ $…$

假如我们之后一个数后面可以跟多少因子，然后这个因子后面…

这就是个递推啊!

设f[i][j]表示以i结尾，长度为j的序列个数。

因为必须是因子，所以转移方程为：

$f[i][j]+=f[k][j-1]$(k为i的因子)

所以要先预处理所有数字的因子，然后进行dp即可。$ans=\sum_{i=1}^nf[i][m]$。

Code

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

const int N = 2002;

ll f[N][N]; // 长度为j，以i结尾的个数
vector<int> p[N];

void init() {
    // p[1].emplace_back(1);
    for(int i = 1;i < N; i++) {
        p[i].emplace_back(1);
        for(int j = 2;j <= i; j++) {
            if(i % j == 0) p[i].emplace_back(j);
        }
    }
}

void solve() {
    init();
    for(int i = 1;i < N; i++) {
        f[i][1] = 1;
        for(auto k : p[i]) {
            for(int j = 2;j < N; j++) {
                f[i][j] = (f[i][j] + f[k][j - 1]) % mod;
            }
        }
    }
    int _; cin >> _;
    while(_--) {
        int n, m; cin >> n >> m;
        ll ans = 0;
        for(int i = 1;i <= n; i++) {
            ans = (ans + f[i][m]) % mod;
        }
        cout << ans << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/08/zoj-4011-happy-sequence/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！