动态规划-牛牛与数组

题目描述

牛牛喜欢这样的数组：
1：长度为n
2：每一个数都在1到k之间
3：对于任意连续的两个数A，B，A<=B 与（A % B != 0）两个条件至少成立一个

请问一共有多少满足条件的数组，对1e9+7取模

输入描述:

输入两个整数n,k

1 ≤ n ≤ 10
1 ≤ k ≤ 100000

输出描述:

输出一个整数

示例1

输入

复制

2 2

输出

复制

示例2

输入

复制

9 1

输出

复制

示例3

输入

复制

3 3

输出

复制

示例4

输入

复制

2 1234

输出

复制

1515011
思路：由于是两个条件至少成立一个。怕少算。所以转换成：没有条件的数组方案总和
-A%B==0&&A!=B的数组方案总和。利用dp，从长度为1的数组往后推。
其中dp[i][j]表示长度为i的数组第i位为j的符合要求的数组方案数

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <iostream>
using namespace std;

typedef long long ll;
const int mod = 1e9+7;
const double PI=3.14159265358;
const int INF=0x3f3f3f3f;

ll dp[12][100010];
//dp[i][j]表示长度为i的数组
//第i位为j的符合要求的数组方案数。
int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,k;
    cin>>n>>k;
    //初始化
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=k;i++)
    {
        //数组长度位1时，值为任何数的可能性都是1;
        dp[1][i]=1;
    }
    //sum记录所有的情况 dum记录A>B且A是B的倍数的情况
    ll sum=0,dum=0;
    //从第二层开始循环
    for(int i=2;i<=n;i++){
        sum=0;

        for(int j=1;j<=k;j++)
        {
            //累加，当i层值为j时
            //i-1层的值为1~k的可能性和。
            sum+=dp[i-1][j];
            sum%=mod;
        }

        for(int j=1;j<=k;j++)
        {
            //当第i层值为j时。
            dum=0;
            //假设第i层的值为B,i-1层的值为A
            //循环A=B的倍数的dp数组
            for(int l=j+j;l<=k;l+=j)
            {
                dum=(dum+dp[i-1][l])%mod;
            }
            //当第i层值为j时，dp[i][j]的值
            //为i-1层所有的可能性的和减去不符合条件的和
            dp[i][j]+=(sum-dum)%mod;
        }
    }
    
    //循环，累加n层数组的值为1~k的可能性和
    ll ans=0;
    for(int i=1;i<=k;i++)
    {
        ans+=dp[n][i];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}