小易非常喜欢拥有以下性质的数列:
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,希望你能帮他求出有多少个是他会喜欢的数列。
[编程题]小易喜欢的数列
//AC代码：
#include<stdio.h>
#include<string.h>
int dp[15][100005];
const int mod=1000000007;
int main(){
int n,k,i,j,q;
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&k)!=EOF){
memset(dp,0,sizeof(dp));
for(i=1;i<=k;i++) dp[1][i]=1;
for(i=2;i<=n;i++){
int sum=0;
for(j=1;j<=k;j++) sum=(sum+dp[i-1][j])%mod;
for(j=1;j<=k;j++){
dp[i][j]=sum;
for(q=j*2;q<=k;q+=j) dp[i][j]=(dp[i][j]-dp[i-1][q]+mod)%mod;
}
}
int res=0;
for(i=1;i<=k;i++) res=(res+dp[n][i])%mod;
printf("%d\n",res);
}
}//用dp[i][j]表示长度为i且必须以j结尾的方法
发表于 2017-08-23 17:56:36
回复(2)
//童山公爵的代码
//C++版，附上了自己的注释，可能会容易懂一点
#include<iostream>
using namespace std;
int dp[11][100005]; //dp[i][j]表示长度为i，尾数为j的合法数列共有多少个
int main(){
int n,k,i,j,mod=1000000007; //mod是题目给出的，防止数字过大
cin>>n>>k;
for(i=1;i<=k;i++)
dp[1][i]=1; //初始化。长度为1，尾数为i的数列只有一个
for(i=2;i<=n;i++){
int sum=0;
for(j=1;j<=k;j++)
sum=(sum+dp[i-1][j])%mod; //dp[i][m]=（所有的dp[i-1][j]相加，再在第i位加上尾数m）- 不合法的数列个数=sum - illegal
for(j=1;j<=k;j++){
int p=2; //这个表示倍数，凡是前一位数字是p*j的都是非法数列，因为 p*j>j && p*j%j==0，违反了第三个条件
int illegal=0;
while(p*j<=k){
illegal=(illegal+dp[i-1][p*j]%mod)%mod;
p++;
}
dp[i][j]=(sum-illegal+mod)%mod; //原本sum>illegal,但是因为illegal和sum都是求的取模，所以这里sum可能<illegal
}
}
int sum=0;
for(int i=1;i<=k;i++)
sum=(sum+dp[n][i])%mod;
cout<<sum;
}
发表于 2019-04-03 17:30:27
回复(0)
/*
如果我们确定这个数列的第一个数是i,那么第二个数可以是1到k中除了是i的约数的任何数。
于是我们定义dp[j][i]表示长度为i最后一个数是j的小易喜欢的数列的数量,然后挨着转移即可
实现请参考参考代码。
*/
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int dp[maxn][15];
int n, k;
int main() {
cin >> n >> k;
dp[1][0] = 1;
for(int i = 1; i <= n; i++) {
int sum = 0;
for(int j = 1; j <= k; j++) {
sum += dp[j][i - 1];
sum %= mod;
}
for(int j = 1; j <= k; j++) {
int sum2 = 0;
for(int z = j + j; z <= k; z += j) {
sum2 += dp[z][i - 1];
sum2 %= mod;
}
dp[j][i] = (sum - sum2 + mod) % mod;
}
}
int ans = 0;
for(int j = 1; j <= k; j++) {
ans += dp[j][n];
ans %= mod;
}
cout << ans << endl;
return 0;
}
发表于 2017-08-13 15:52:50
回复(1)
听过左神讲解后才学会的。
当确定了第一个数后，第二个数可以取哪些？依次进行就是递归的方法。
从递归的尾部观察，将整个过程倒过来，用循环来计算，就是最高效率的算法了。
在这里有个问题是从前向后循环求解还是从后向前求解，两种方法是有效率差异的。我开始时是用了从前向后来循环求解，结果超时；后来参考左神代码，发现从后向前来循环求解，在减去不符合条件3的值时，减的次数会少很多（k比较大时），最终AC。
代码如下，包含递归的方法和非递归的方法~
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
class Solution {
private:
int n;
int k;
long res;
int mod = 1000000007;
private:
void init() {
cin >> n >> k;
res = 0;
}
void write_result() {
cout << res;
}
void calculate_result() {
if (n == 0 || k == 0)
return;
//res = func1(n + 1, 1);
res = func2();
}
int func1(int index, int pre_num) {
int count = 0;
if (index < 2)
count = 1;
else {
for (int i = 1; i < pre_num; i++)
if (pre_num%i != 0)
count += func1(index - 1, i);
for (int i = pre_num; i <= k; i++)
count += func1(index - 1, i);
}
return count;
}
long func2() {
vector<long> vt(k + 1, 1);
long vtsum = k;
vector<vector<int>> noncdt(k + 1);
for (int i = 1; i <= k; i++) {
for (int j = i + i; j <= k; j += i) {
noncdt[i].push_back(j);
}
}
for (int col = 1; col < n; col++) {
long newsum = 0;
for (int row = 1; row <= k; row++) {
long del = 0;
for (auto d : noncdt[row]) {
del += vt[d];
del %= mod;
}
vt[row] = (vtsum - del + mod) % mod;
newsum += vt[row];
newsum %= mod;
}
vtsum = newsum;
}
return vtsum;
}
public:
void solve() {
init();
calculate_result();
write_result();
}
};
int main()
{
Solution s;
s.solve();
return 0;
}
发表于 2017-08-31 21:32:04
回复(4)
#include<iostream>
#include<vector>
using namespace std;
const int MAX_VAL = 1000000007;
int main(){
/*
动态规划有两个关键点：时间步与状态空间；
通常dp[i,j]:i对应时间步，j对应状态空间的取值
当题目中出现从一个状态到另一种状态的时候可以考虑动态规划
对于从1开始还是从0开始，建议按照题目要求从1或者0开始，否则容易出错。同时从一开始时要注意
循环的终止条件是<n还是<=n
*/
// 时间复杂度O(n(k+ k+k/2+k/3+...+k/k)); 空间复杂度O(k)
int n, k;
while(cin>>n>>k){
vector<int> dp(k+1,1);
int sum = k;
for(int i=1; i<n; i++){
for(int j=1; j<=k; j++){ // i-th 的位置取j时
dp[j] = sum;
for(int z=2*j; z<=k; z=z+j){//排除不满足性质的情况
dp[j] = (dp[j]-dp[z]+MAX_VAL)%MAX_VAL;
}
}
sum = 0;
for(int j=1; j<=k; j++){
sum = (sum+dp[j])%MAX_VAL;
}
}
cout<<sum<<endl;
dp.clear();
}
return 0;
}
#include<vector>
using namespace std;
const int MAX_VAL = 1000000007;
int main(){
/*
动态规划有两个关键点：时间步与状态空间；
通常dp[i,j]:i对应时间步，j对应状态空间的取值
当题目中出现从一个状态到另一种状态的时候可以考虑动态规划
对于从1开始还是从0开始，建议按照题目要求从1或者0开始，否则容易出错。同时从一开始时要注意
循环的终止条件是<n还是<=n
*/
// 时间复杂度O(n(k+ k+k/2+k/3+...+k/k)); 空间复杂度O(k)
int n, k;
while(cin>>n>>k){
vector<int> dp(k+1,1);
int sum = k;
for(int i=1; i<n; i++){
for(int j=1; j<=k; j++){ // i-th 的位置取j时
dp[j] = sum;
for(int z=2*j; z<=k; z=z+j){//排除不满足性质的情况
dp[j] = (dp[j]-dp[z]+MAX_VAL)%MAX_VAL;
}
}
sum = 0;
for(int j=1; j<=k; j++){
sum = (sum+dp[j])%MAX_VAL;
}
}
cout<<sum<<endl;
dp.clear();
}
return 0;
}
发表于 2019-03-21 22:04:33
回复(0)
40%通过率，迭代时间超限....
n,k=[int(i) for i in input().strip('\n').split(' ')]
def find(n,k,a):
count=0
if a==0:
for i in range(1,k+1):
count+=find(n-1,k,i)
return count
elif n==1:
for i in range(1,k+1):
if i<=a or i%a!=0:
count+=1
return count
else:
for i in range(1,k+1):
if i<=a or i%a!=0:
count+=find(n-1,k,i)
return count
print(find(n,k,0))
def find(n,k,a):
count=0
if a==0:
for i in range(1,k+1):
count+=find(n-1,k,i)
return count
elif n==1:
for i in range(1,k+1):
if i<=a or i%a!=0:
count+=1
return count
else:
for i in range(1,k+1):
if i<=a or i%a!=0:
count+=find(n-1,k,i)
return count
print(find(n,k,0))
编辑于 2017-09-08 16:11:58
回复(0)
哪位大神帮看看这题用回溯算法怎么能不超内存？
拜托拜托
importjava.util.ArrayList;
importjava.util.Scanner;
publicclassMain{
publicstaticintnum =0;
publicstaticvoidmain(String [] args){
Scanner scan =newScanner(System.in);
intn = scan.nextInt();
intk = scan.nextInt();
BackTracking(k,n,newArrayList<Integer>());
System.out.print(num);
}
publicstaticvoidBackTracking(intk,intn,ArrayList<Integer> list){
if(list.size()>=n){
num++;
return;
}
for(inti =1;i<=k;i++){
if(list.size()==0){
list.add(i);
BackTracking(k,n,list);
list.remove(list.get(list.size()-1));
}elseif(i>=list.get(list.size()-1)||list.get(list.size()-1)%i!=0){
list.add(i);
BackTracking(k,n,list);
list.remove(list.get(list.size()-1));
}
}
}
}
发表于 2017-08-13 15:27:15
回复(1)
import java.util.*;
public class Sim {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[][] dp = new int[k+5][n+5];
dp[1][0] = 1;
for(int i = 1; i <= n; i++) {
int sum = 0;
for(int j = 1; j <= k; j++) {
sum += dp[j][i - 1];
sum %= 1000000007;
}
for(int j = 1; j <= k; j++) {
int sum2 = 0;
for(int z = j + j; z <= k; z += j) {
sum2 += dp[z][i - 1];
sum2 %= 1000000007;
}
dp[j][i] = (sum - sum2 + 1000000007) % 1000000007;
}
}
int result = 0;
for(int i = 0; i <= k; i++) {
result += dp[i][n];
result %= 1000000007;
}
System.out.println(result);
}
}
编辑于 2017-08-12 18:33:48
回复(15)
#include <bits/stdc++.h>
using namespace std;
const int M = 1e9+7;
int main(){
int n, k, s=0;
scanf("%d%d", &n, &k);
int dp[15][100003];
memset(dp, 0, sizeof(dp));
for(int i=1;i<=k;i++)
dp[1][i] = 1;
for(int i=2;i<=n;i++){
int t=0;
for(int j=1;j<=k;j++)
t = (t+dp[i-1][j])%M;
for(int j=1;j<=k;j++){
dp[i][j] = t;
for(int h=2*j;h<=k;h+=j)
dp[i][j] = (dp[i][j]-dp[i-1][h]+M)%M;
}
}
for(int i=1;i<=k;i++)
s = (s+dp[n][i])%M;
printf("%d\n", s);
return 0;
}
发表于 2020-09-28 09:23:10
回复(0)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <forward_list>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l + r) >> 1)
#define midmid ((r + mid) >> 1)
#define LONG_LONG_MIN -9223372036854775808ll
#define LONG_LONG_MAX 9223372036854775807ll
using namespace std;
typedef long long int ll;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
ll dp[12][MAXN],sum[12];
ll n,k;
vector<int> p[MAXN];
bool can[MAXN];
int main(){
scanf("%lld%lld",&n,&k);
memset(can,true,sizeof(can));
for(int i = 2; i <= k; ++i){
p[i].push_back(1);
for(int j = i + i; j <= k; j += i){
p[j].push_back(i);
can[j] = false;
}
// printf("%d: ",i);
// for(int j = 0; j < p[i].size(); ++j){
// printf("%d ",p[i][j]);
// }
// printf("\n");
}
memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum));
for(ll i = 1; i <= k; ++i){
dp[n][i] = 1;
sum[n] += 1;
}
for(ll i = n - 1; i >= 1; --i){
for(ll j = 1; j <= k; ++j){
dp[i][j] = sum[i + 1];
for(ll s = 0; s < p[j].size(); ++s){
dp[i][j] = dp[i][j] - dp[i + 1][p[j][s]];
if(dp[i][j] < 0){ dp[i][j] += MOD;}
}
sum[i] = sum[i] + dp[i][j];
sum[i] %= MOD;
}
}
printf("%lld\n",sum[1]);
return 0;
} 考虑动态规划
dp[i][j]表示第i位为j的方案数
dp[i][j] = sum(dp[i + 1][k]) k为所有除j外非j的因子
这个状态转移的k可以转换成，先求出所有的k，然后减去dp[i + 1][k] k是j外为j的因子。因为对于一个数来说，一般因子比非因子要少一些（考虑欧拉函数）
那么对于前半部分，因为其实就是dp[i + 1]下所有的和，这部分预先可以求一个前缀和，可以省掉一个k的循环，O（k * k）一定会超时
然后对于后半部分，如果对于每次j，都去算一次因子集合，复杂度是O（sqrt(k) * k），会比较危险，那么考虑利用筛法预处理出所有因子即可。
这里筛法可以不用线性筛，因为这里的klogk是加法
总复杂度为O（klogk + n * k）
发表于 2019-09-13 06:19:27
回复(0)
python elegant solution
pass 80%
n, k = list(map(int, input().strip().split()))
# dp[i][j] += dp[i-1][m] for m in k
dp = [[0] * (k + 1) for _ in range(n)]
for j in range(1, k + 1):
dp[0][j] = 1
for i in range(1, n):
total = sum(dp[i - 1])
for j in range(1, k + 1):
dp[i][j] = total
for m in range(2 * j, k + 1, j):
dp[i][j] -= dp[i - 1][m]
print(sum(dp[n - 1]) % 1000000007)
发表于 2019-08-07 16:13:03
回复(0)
【思路，动态规划】dp[i][j]代表个数，i为序列长度，j为最后一位数字是几。每次都是用i-1行的数据来计算i行的数据，每个sum相当于把上一行的所有dp都加了一遍，因为数字可能出现这么多情况；每个illegal相当于把不满足条件的数据都加了一遍，最后用sum-illegal，就得到了该dp[i][j]点的值了。最终将题目所要求的的第n行（即i=n）所有数据相加，就是最后的结果。
#include <iostream>
using namespace std;
int main(void)
{
int mod = 1000000007;
int dp[11][100005] = { 0 };//dp[i][j] ,i为数列长度(n)，j为数列末尾的数字(k)
// memset(dp, 0, sizeof(dp));
int n, k;
cin >> n >> k;
for (int j = 1; j <= k; j++)
dp[1][j] = 1;
for (int i = 2; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= k; j++)
sum = (sum + dp[i - 1][j]) % mod;
for (int j = 1; j <= k; j++)
{
int mul = 2;
int illegal = 0;
while (mul*j <= k)
{
illegal = (illegal + dp[i - 1][mul*j]) % mod;
mul++;
}
dp[i][j] = (sum - illegal + mod) % mod;
}
}
int res = 0;
for (int i = n, j = 1; j <= k; j++)
res = (res + dp[i][j]) % mod;
cout << res << endl;
return 0;
}
发表于 2019-05-06 22:35:36
回复(0)
import java.util.Scanner;
public class Problem_201703 {
private static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int n = scan.nextInt();
int k = scan.nextInt();
//dp[i][j]表示长度为i的序列以j结束数字的数列个数
//dp[i][j] = dp[i - 1][m] (1 <= m <= k)并且(m,j)是一个有效的序列
int[][] dp = new int[n + 1][k + 1];
dp[0][1] = 1;
for (int i = 1; i <= n; i++) {
int sum = 0;
//所有可能组合
for (int j = 1; j <= k; j++) {
sum = (sum + dp[i - 1][j]) % MOD;
}
for (int j = 1; j <= k; j++) {
//删除所有不满足条件的情况，类似素数筛选的过程
int invalid = 0;
int p = 2;
while (p * j <= k) {
//dp[i - 1][p * j]违反了A % B != 0，因此剔除
invalid = (invalid + dp[i - 1][p * j]) % MOD;
p++;
}
//为初始化添加增量
dp[i][j] = (sum - invalid + MOD) % MOD;
}
}
int res = 0;
for (int i = 1; i <= k; i++) {
res = (res + dp[n][i]) % MOD;
}
System.out.println(res);
}
scan.close();
}
}
发表于 2018-08-10 16:19:46
回复(0)
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)
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main()
{
int mod=1000000007;
int n;
int k;
cin>>n>>k;
int state[n+1][k+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<k+1;j++)
{
state[i][j]=0;
//cout<<state[i][j]<<' ';
}
//cout<<endl;
}
state[0][1]=1;
for(int i=1;i<=n;i++)
{
int sum = 0;
for(int j=1;j<=k;j++)
{
sum=(sum+state[i-1][j])%mod;
}
for(int j=1;j<=k;j++)
{
int invalid = 0;
int p=2;
while(p*j<=k)
{
invalid = (invalid + state[i-1][p*j])%mod;
p++;
}
state[i][j]=(sum-invalid+mod)%mod;
}
}
int sum = 0;
for(int i=1;i<=k;i++)
sum=(sum+state[n][i])%mod;
cout<<sum<<endl;
return 0;
}
发表于 2017-08-15 11:29:47
回复(0)
思路与 @童山公爵 一致
因为简单的用动态规划会超时，所以在计算res[i][j]的时候，先将res中i-1行的元素求和，然后减去其中不符合要求的数字。
import java.util.Scanner; public class Main { static final int MOD = 1000000007; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); //res[i][]j表示第i个数字为j的次数 int[][] res = new int[n + 1][k + 1]; res[0][1] = 1; for (int i = 1; i <= n; i++) { int sum = 0; for (int j = 1; j <= k; j++) sum = (sum + res[i - 1][j]) % MOD; for (int j = 1; j <= k; j++) { int p = 2; int invalid = 0; while (p * j <= k) { //计算不符合要求的数字和 invalid = (invalid + res[i - 1][p * j]) % MOD; p++; } res[i][j] = (sum - invalid + MOD) % MOD; } } int sum = 0; for (int i = 1; i <= k; i++) sum = (sum + res[n][i]) % MOD; System.out.println(sum); sc.close(); } }
发表于 2017-08-14 11:53:51
回复(1)
importjava.util.Arrays;
importjava.util.Scanner;
publicclassMain {
publicstaticvoidmain(String[] args) {
Scanner in = newScanner(System.in);
while(in.hasNext()) {
intn = in.nextInt();
intk = in.nextInt();
System.out.println(solve(n, k));
}
}
privatestaticintsolve(intn, intk) {
intMAX_VALUE = 1000000007;
//表示第n个数字以k结尾的组合数
int[][] dp = newint[n][k + 1];
//数字长度为i-1的总组合数
intlastSum = k;
//数字长度为i的的总组合数
intnowSum = 0;
//长度为1时可以以任意数字结尾,组合数为1
Arrays.fill(dp[0], 1);
for(inti = 1; i < n; i++) {
nowSum = 0;
for(intj = 1; j <= k; j++) {
dp[i][j] = (dp[i][j] + lastSum) % MAX_VALUE;
/**
* 减去上一个数子除以当前数字为0的情况
* j == 1时需要计算n次
* j == 2时需要计算n / 2次
* j == 3时需要计算n / 3次
* ....
* 求大神指点这个复杂度怎么算
*/
for(intz = j + j; z <= k; z += j) {
dp[i][j] = (dp[i][j] - dp[i - 1][z] + MAX_VALUE) % MAX_VALUE;
}
nowSum = (dp[i][j] + nowSum) % MAX_VALUE;
}
lastSum = nowSum;
}
returnnowSum;
}
}
发表于 2017-08-14 10:05:34
回复(2)
state[i][j]表示整个状态空间，其中i(1<=i<=n)表示数列的长度，j(1<=j<=k)表示数列长度为i且以数字j结尾。
递推关系有：state[i][j] += state[i-1][m] (1<=m<=k, 并且(m,j)是个合法的数列)，但是直接按照递推关系，用三层for循环会超时。为此可以先将长度为i-1的合法数列求和(记为sum)。然后对于数列长度为i的每一个j，求出数列长度为i-1时非法的序列个数（记为invalid）,即有state[i][j] = sum - invalid。
对于invalid求取，可以参照素数筛选。算法的时间复杂度大概为O(nkloglogk)
import java.util.Scanner;
public class Main {
static final int mod = 1000000007;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[][] state = new int[n+1][k+1];
state[0][1] = 1;
for(int i=1; i<=n; i++) {
int sum = 0;
for(int j=1; j<=k; j++) {
sum = (sum + state[i-1][j]) % mod;
}
for(int j=1; j<=k; j++) {
int invalid = 0;
int p = 2;
while(p*j <= k) {
invalid = (invalid + state[i-1][p*j]) % mod;
p++;
}
state[i][j] = (sum - invalid + mod) % mod;
}
}
int sum = 0;
for(int i=1; i<=k; i++) {
sum = (sum + state[n][i]) % mod;
}
System.out.println(sum);
scanner.close();
}
}
编辑于 2017-08-12 23:45:33
回复(44)
问题信息
通过挑战的用户
查看代码-
2023-02-08 15:40:42
-
2022-09-16 09:21:11
-
2022-09-10 17:17:29
-
2022-08-29 09:57:48
-
2022-08-18 11:26:19
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
