牛牛与数组DP

缺乏、安全感 2021-11-16 23:08 326阅读 0赞

链接：[https://ac.nowcoder.com/acm/problem/21738][https_ac.nowcoder.com_acm_problem_21738]  
来源：牛客网  
  
牛牛喜欢这样的数组：  
1：长度为n  
2：每一个数都在1到k之间  
3：对于任意连续的两个数A，B，A<=B 与（A % B != 0） 两个条件至少成立一个  
  
请问一共有多少满足条件的数组，对1e9+7取模

**思路：**如果正着计算容易出现遗漏，所以我们只用找 “A>B&&A是B的倍数”的方案数，然后用总数减去这个方案数就是答案。

思考用dp来解决这个问题，设dp\[i\]\[j\]表示长度为 i 的数组第 i 位为 j 的符合要求的数组方案数。(1<=i<=n 1<=j<=k)

代码逻辑：n个数的数组，先初始化dp\[1\]\[i\] = 1。三重循环，通过优化计算得时间复杂度为O(n^2 logn)，即可以计算出

T(n) = 5\*10^6。在循环中先计算长度为 i 时所有可能的数组个数（不考虑题目的条件），用sum记录。然后计算确定 j 时的（A>B && A是B的倍数）的方案数，用dum记录。然后用sum-dum，计算出dp\[i\]\[j\]。

（计算中别忘了取模）

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 3e6+10;
    const int modd = 1e9+7;
    typedef long long ll;
    const int inf = 0x3f3f3f3f;
    int dp[20][100000];
    
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n,k;
        cin>>n>>k;
        ll ans = 0;
        for(int j = 1;j <= k;++j){
            dp[1][j] = 1;
        }
        int sum = 0,dum = 0;
        for(int i = 2;i <= n;++i){
            sum = 0;
            for(int j = 1;j <= k;++j){
                sum += dp[i-1][j];
                sum %= modd;
            }
            for(int j = 1;j <= k;++j){
                dum = 0;
                for(int x = 2*j;x <= k;x+=j){
                    dum += dp[i-1][x];
                    dum %= modd;
                }
                dp[i][j] = (sum-dum)%modd;
            }
        }
        for(int i = 1;i <= k;i++){
            ans += dp[n][i];
            ans %= modd;
        }
        cout<<ans<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_problem_21738]: https://ac.nowcoder.com/acm/problem/21738