首页 > 试题广场 >

小易喜欢的数列

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

热度指数：11251 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输出

算法知识视频讲解

JavaScript

doramc

nodejs版本。。

var readline = require('readline')

const rl = readline.createInterface({

input: process.stdin,

output: process.stdout

})

rl.on('line', function (line) {

var tokens = line.split(' ')

console.log(dpHelper3(1, +tokens[0], +tokens[1]));

})

function dpHelper3(prev, n, k) {

var dp = [], sum = 0, m=1e9+7;

dp[0] = 0;

for (var i = 1; i <= k; i++) {

dp[i] = 1;

}

for (var j = 1; j < n; j++) {

sum = dp.reduce(function (pre, val) { return (pre + val) % m });

for (var p = 1; p <= k; p++) {

var noneValid = 0;

for(var row = 2*p; row <=k; row+=p){

noneValid += dp[row];

noneValid %= m;

}

dp[p] = (sum - noneValid) % m;

}

}

return dp.reduce(function (pre, val) { return (pre + val) % m });

}

发表于 2017-09-07 14:59:05 回复(0)

JavaScript

风萧萧梦也潇潇

//用二维数组的动态规划
var M=1e9+7;
var line=readline().split(' ');
var n=+line[0],k=+line[1];
var dp=Array(n+1);//dp[i][j]表示第i个数为j有多少种
for(var i=1;i<=n;i++){
    dp[i]=Array(k+1);
}
//dp[1][i]永远是1，dp[i][1]永远是1;
for(var i=1;i<=n;i++){
    dp[i][1]=1;
}
for(var i=0;i<=k;i++){
    dp[1][i]=1;
}
//果然三层循环会超时，得用总和-无效
for(var i=2;i<=n;i++){
    var sum=0;
    for(var u=1;u<k+1;u++){
        sum=(sum+dp[i-1][u])%M;
    }
    for(var j=2;j<=k;j++){
        dp[i][j]=0;
        var invalid=0;
        for(var d=2*j;d<=k;d+=j){
            invalid=(invalid+dp[i-1][d])%M;
        }
        dp[i][j]=(M+sum-invalid)%M;
    }
}

var result=0;
for(var i=1;i<=k;i++){
    result=(result+dp[n][i])%M;
}
print(result)

//其实本题还可以简化为一维数组，大大减小空间，注意到每次数组赋值只与前一次有关，而且算无效数据累加时只与该数后面的数（2倍、3倍等）有关
var M=1e9+7;
var line=readline().split(' ');
var n=+line[0],k=+line[1];
var dp=Array(k+1);//dp[i]表示每次，最大数为i的时候有多少种
//初始全为1表示只有只能有一个数的时候只会有一种排列
for(var i=1;i<=k;i++){
    dp[i]=1;
}
//果然三层循环会超时，得用总和-无效
for(var i=2;i<=n;i++){
    var sum=0;
    for(var u=1;u<k+1;u++){
        sum=(sum+dp[u])%M;
    }
    for(var j=2;j<=k;j++){
        var invalid=0;
        for(var d=2*j;d<=k;d+=j){
            invalid=(invalid+dp[d])%M;
        }
        dp[j]=(M+sum-invalid)%M;
    }
}
var result=0;
for(var i=1;i<=k;i++){
    result=(result+dp[i])%M;
}
print(result)

编辑于 2017-08-16 11:07:34 回复(0)