2. 序列
(sequence.cpp/c/pas)
【问题描述】
一个长度为k的整数序列b1，b2，…，bk（1≤b1≤b2≤…≤bk≤N）称为“好序列”当且仅当后一个数是前一个数的倍数，即bi+1是bi的倍数对任意的i（1≤i≤k-1）成立。
给定N和k，请算出有多少个长度为k的“好序列”，答案对1000000007取模。
【输入】
输入文件名为sequence.in。
输入共1行，包含2个用空格隔开的整数N和k。
【输出】
输出文件名为sequence.out。
输出共1行，包含一个整数，表示长度为k的“好序列”的个数对1000000007取模后的结果。
【输入输出样例】
sequence.in
sequence.out
3 2
5
【输入输出样例说明】
“好序列”为：[1,1]，[1,2]，[1,3]，[2,2]，[3,3]。
【数据说明】
对于40%的数据，1≤N≤30，1≤k≤10。
对于100%的数据，1≤N≤2000，1≤k≤2000。
分析：
二维简单dp，状态转移方程f[i,j]:=(f[i,j]+f[i*k,j-1]) mod 1000000007。
代码：
const maxn=2000; var f:array[1..maxn,1..maxn] of longint; n,m,ans:longint; procedure init; var i:longint; begin readln(n,m); for i:=1 to n do f[i,1]:=1; end; procedure main; var i,j,k:longint; begin for j:=2 to m do for i:=1 to n do for k:=1 to n div i do begin if f[i*k,j-1]=0 then break; f[i,j]:=(f[i,j]+f[i*k,j-1]) mod 1000000007; end; for i:=1 to n do ans:=(ans+f[i,m]) mod 1000000007; writeln(ans); end; begin assign(input,'sequence.in');reset(input); assign(output,'sequence.out');rewrite(output); init; main; close(input);close(output); end.
