[编程题] 小易喜欢的数列 dp

https://www.nowcoder.com/question/next?pid=6291726&qid=112729&tid=12736753

[编程题] 小易喜欢的数列

时间限制：1秒

空间限制：32768K

小易非常喜欢拥有以下性质的数列:
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

输出例子1:

3

　　dp[i][j]表示第i个位置放的数是j的时候的合法方案是多少。
　 转移：dp[i - 1][j] = sigma(dp[i][1...j]) - (sigma(dp[i][j的因子]);

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn = 1e5 + ;

const int MOD = 1e9 + ;

LL dp[][maxn];

void add(LL &x, LL y) {

    x = (x + y + MOD) % MOD;

}

int prime[maxn][];

void init_prime() {

    for (int i = ; i <= maxn - ; ++i) {

        if (prime[i][]) continue; // 这个数i不是质数

        for (int j = i; j <= maxn - ; j += i) {

            prime[j][++prime[j][]] = i;

        } //prime[12] = {2, 3}

    }

}

vector<int> vc[maxn];

void ca(int num, int to, int now) {

    if (now > num / ) return;

    if (num % now == ) vc[num].push_back(now);

    else return;

    if (to == ) to = ;

    for (int i = to; i <= prime[num][]; ++i) {

        ca(num, i, now * prime[num][i]);

    }

}

void show() {

    int f = ;

    for (int i = ; i < vc[f].size(); ++i) {

        cout << vc[f][i] << " ";

    }

    cout << endl;

}

void work() {

    int n, k;

    cin >> n >> k;

    int now = ;

    LL sum = k;

    for (int i = ; i <= k; ++i) {

        dp[][i] = ;

    }

    init_prime();

    for (int i = ; i <= k; ++i) {

        ca(i, , );

    }

//    show();

    for (int i = n - ; i >= ; --i) {

        now = !now;

        dp[now][] = sum;

        for (int j = ; j <= k; ++j) {

            dp[now][j] = sum;

//            for (int f = 2 * j; f <= k; f += j) {

//                add(dp[now][j], -dp[!now][f]);

//            }

            for (int f = ; f < vc[j].size(); ++f) {

                add(dp[now][j], -dp[!now][vc[j][f]]);

            }

        }

        sum = ;

        for (int j = ; j <= k; ++j) {

//            sum[j] = dp[now][j];

//            add(sum[j], sum[j - 1]);

            add(sum, dp[now][j]);

        }

    }

    LL ans = ;

    for (int i = ; i <= k; ++i) {

        add(ans, dp[now][i]);

    }

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

[编程题] 小易喜欢的数列 dp的相关教程结束。