題目描述

　　一個長度為k的整數序列b1，b2，...，bk（1≤b1≤b2≤...≤bk≤N）稱為“好序列”當且僅當后一個數是前一個數的倍數，即bi+1是bi的倍數對任意的i（1≤i≤k-1）成立。

　　給定N和k，請算出有多少個長度為k的“好序列”，答案對1000000007取模。

?

輸入格式

　　一行，包含2個用空格隔開的整數N和k。

?

輸出格式

　　一行，包含一個整數，表示長度為k的“好序列”的個數對1000000007取模后的結果。

?

輸入樣例

3 2

?

輸出樣例

5

?

數據規模

　　對于40%的數據，1≤N≤30，1≤k≤10。

　　對于100%的數據，1≤N≤2000，1≤k≤2000。

?

題解

　　我們枚舉因子來傳遞狀態給倍數即可，這里可以用滾動數組優化。

#include <iostream> #include <fstream>#define MAX_N 2001 #define MAX_M 2001#define MOD 1000000007using namespace std;int n, m; int dp[MAX_N]; int ans;int main() {cin >> n >> m;for(register int i = n; i; --i){dp[i] = 1;}for(register int i = 2; i <= m; ++i){for(register int j = n >> 1; j; --j){for(register int k = j << 1; k <= n; k += j){dp[k] += dp[j];if(dp[k] >= MOD) dp[k] -= MOD;}}}for(register int i = n; i; --i){ans += dp[i];if(ans >= MOD) ans -= MOD;}cout << ans;return 0; } 參考程序

?

轉載于:https://www.cnblogs.com/kcn999/p/10805301.html

總結

以上是生活随笔為你收集整理的【题解】序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。