牛牛与数组

题目链接

题意：

 中文的，而且说的很明白，但是要注意，这个数组中的数可以重复

思路：

• 1、dp状态 dp[i,j]表示了长度为i并以j结尾的数组符合条件的方案数有多少种
• 2、状态转移方程 dp[i,j] = sum(dp[i - 1][k] (k <= j) + dp[i - 1][x] (j % x != 0))

最暴力的dp方式是跑3个循环，这样时间复杂度是O( * )
由于时间是1000ms所以暴力dp肯定是过不了的
所以我们可以转化一下思路 采用 dp[i,j] = sum - dum 其中 sum = Sum(dp[i - 1][x]) (x >=1&& x <= k),dum = Sum(dp[i - 1][y] (y >= 1 && y <= k &&x % y != 0))
即采取了总和减去不符合条件的值即可得到符合条件的dp[i,j]
最后答案即为sum(dp[n,j]) (j >= 1&& j <= k)

ac 代码

 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 100000 + 5;
const int mod = 1e9 + 7;


ll pre[maxn],suf[maxn];
ll dp[12][maxn];
//状态,dp[i,j]表示了长度为i并以j结尾的数组符合条件的方案数有多少种

void Solve(int n,int k)
{
    for(int i = 1; i <= k; i++)  dp[1][i] = 1;//对于长度为1的数组，不管以什么数结尾，都是1种
    ll sum = 0,dum = 0;
    //如果三层循环暴力跑，一定会时间超限
    //所以采用求出上一层所有情况的数量 减去 其中是当前结尾数的倍数的数量
    //最后将其求和
    for(int i = 2; i <= n; i++){
        sum = 0;
        for(int j = 1; j <= k; j++) sum = (sum % mod + dp[i - 1][j] % mod) % mod;
        for(int j = 1; j <= k; j++){
            dum = 0;
            for(int q = j + j; q <= k; q += j) dum = (dum % mod + dp[i - 1][q] % mod) % mod;
            dp[i][j] = (sum - dum) % mod;
        }
    }
    ll res = 0;
    for(int i = 1; i <= k; i++) res = (res % mod + dp[n][i] % mod) % mod;
    cout<<res<<endl;
}

int main()
{
    int n,k;
    cin>>n>>k;
    Solve(n, k);
    return 0;
}