题意：在1-n中选可重复的k个数组成一个数列，其中 b【i+1】 % b【i】 = 0 ,问你有多少种情况
解题思路：dp，每增加一个数只与现在数列的最后一个数有关。
解题代码：
1 // File Name: d.c 2 // Author: darkdream 3 // Created Time: 2014年04月07日 星期一 01时29分35秒 4 5 #include<stdio.h> 6 #include<string.h> 7 #include<stdlib.h> 8 #include<time.h> 9 #include<math.h> 10 #include<limits.h> 11 #define M 1000000007 12 long long ans[2001][2001]; 13 int a[2001][2001]; 14 int num[2001]; 15 int main(){ 16 17 //freopen("/home/darkdream/problem/input.txt","r",stdin); 18 //freopen("/home/darkdream/problem/output.txt","w",stdout); 19 int n , k ; 20 scanf("%d %d",&n,&k); 21 memset(a,0,sizeof(a)); 22 memset(ans,0,sizeof(ans)); 23 memset(num,0,sizeof(num)); 24 for(int i = 1;i <= n; i ++) 25 { 26 for(int j = 1;j <= i; j++) 27 { 28 if(i % j == 0 ) 29 { num[i] ++ ; 30 a[i][num[i]] = j; 31 } 32 } 33 } 34 for(int i = 1;i <= n;i ++) 35 ans[1][i] = 1; 36 for(int i = 2;i <= k;i ++) 37 { 38 for(int j = 1;j <= n;j ++) 39 for(int s = 1; s <= num[j]; s++) 40 { ans[i][j] = ( ans[i][j]+ ans[i-1][a[j][s]]) % M; 41 // printf("%I64d %d %d ",ans[i-1][a[j][s]],i,j); 42 } 43 } 44 long long rans = 0 ; 45 for(int i = 1; i <= n;i ++) 46 rans = (rans + ans[k][i]) % M ; 47 printf("%I64d ",rans); 48 return 0 ; 49 }