小易喜欢的数列

TLE方法(回溯)：

public class Main {

    private static int ans = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();
        boolean[] visited = new boolean[n+1];
        backtracking(new ArrayList<Integer>(), n, k);
        System.out.println(ans);
    }

    private static void backtracking(ArrayList<Integer> list, int n, int k){
        if(n==0){
            ans++;
            ans = ans % 1000000007;
            return;
        }
        for(int i = 1;i<=k;i++){
            if(list.size()==0 || (list.size()!=0 && (list.get(list.size()-1)<=i || list.get(list.size()-1)%i!=0))) {
                list.add(i);
                backtracking(list, n - 1, k);
                list.remove(list.size()-1);
            }
        }
    }
}

思路：

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)

TLE方法(DP):

public class Main {
    static final int mod = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();
        int[][] state = new int[n+1][k+1];

        state[0][1] = 1;
        for(int i = 1;i<=n;i++){
            for(int j=1;j<=k;j++){
                for(int m=1;m<=k;m++){
                    if(m<=j || m%j!=0)
                        state[i][j]+=state[i-1][m];
                }
            }
        }
        int sum = 0;
        for(int i = 1;i<=k;i++){
            sum = (sum+state[n][i])%mod;
        }
        System.out.println(sum);
    }
}

AC方法：

public class Main {
    static final int mod = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.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;
                //满足的条件为: A<=B || A%B!=0
                //则不满足的条件为: A>B && A%B==0
                //此处即为 (p*j,j)
                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);
    }
}

//用动态规划做,列出动态规划式子

import java.util.*;

public class Main{
    public static final int mod = 1000000007;
    public static void main(String[ ] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int k = input.nextInt();
        int[][] temp = new int[n+1][k+1];
        
        /*[0 1 2       (k-1) k]
        0  0 1 0             0
        1  0 
          
         
        (n-1)
        n
        */
        
        //动态规划,其中 invaild = temp[i-1][A]   A即为满足A mod B ==0
        //temp[i][j] = invalid-(temp[i-1][1] +.....+ temp[i-1][k])
        
        int sum, invalid, z;
        temp[0][1] = 1; //使得n=1时,各k列能初始化为1
        for(int i=1;i<=n;i++){
            sum = 0;
            for(int j=1;j<=k;j++){
                sum = (sum + temp[i-1][j]) % mod;
            }
            for(int j=1;j<=k;j++){
                invalid = 0;
                z = 2;
                while(j*z<=k){
                    invalid = (invalid + temp[i-1][***od;
                    z++;
                }
                temp[i][j] = (sum - invalid + mod) % mod;  //防止为负数
            }
        }
        sum = 0;
        for(int j=1;j<=k;j++){
            sum = (sum + temp[n][j]) % mod; //最后的结果为最后一行所有可能的和
        }
        System.out.println(sum);
    }
}

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();
    }

}