题目：一道难题

思路：动态规划

1. 题目要求无重复的子序列的个数
2. 当n==m时，答案为是2^m
3. 当n!=m时，将n分块，每一块为1-m。对于某一块的某一个元素p，讨论以该元素结尾的子序列个数，答案为以每个元素结尾的子序列个数之和
4. 对于第一块的元素，下标为i，如果以当前元素结尾，子序列的个数为2^i
5. 对于其他块，以某一个元素p为例，以p结尾的子序列个数，可以是上一块大于等于p的元素的子序列数之和，也可以是当前块比p小的元素的子序列数之和

假如n=7,m=3，以下是dp的演化过程，[]代表[]后面的数来自[]中的数之和

• n: 1 2 3 1 2 3 1
• dp: [1 2 4] 7
• dp: 1 [2 4 7] 13
• dp: 1 2 [4 7 13] 24
• dp: 1 2 4 [7 13 24] 44
• ans: 1+2+4+7+13+24+44=96

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		String[] s=br.readLine().split(" ");
		int p=1000000007;
		int t=Integer.parseInt(s[0]);
		for(;t>0;t--) {
			s=br.readLine().split(" ");
			int n=Integer.parseInt(s[0]);
			int m=Integer.parseInt(s[1]);
			long[] dp=new long[n+1];
			dp[1]=1l;
			//记录长度为m的块的和
			long sum=1l;
			//答案
			long ans=2l;
			//初始化第一块的值
			for(int i=2;i<=Math.min(n, m);i++) {
				dp[i]=(dp[i-1]*2l)%p;
				sum=(sum+dp[i])%p;
				ans=(ans+dp[i])%p;
			}
			//记录其他快元素的值
			for(int i=Math.min(n, m)+1;i<=n;i++) {
				dp[i]=sum;
				sum=(sum+dp[i])%p;
				//防止sum变成负数
				sum=(sum-dp[i-m]+p)%p;
				ans=(ans+dp[i])%p;
			}
			pw.println(ans);
		}
		pw.flush();
	}
}