CF 414B Mashmokh and ACM 动态规划

题意：

　　给你两个数n和k。求满足以下条件的数列有多少个。

　　这个数列的长度是k： b[1], b[2], ……, b[k]。并且 b[1] <= b[2] <= …… <= b[k] <= n；

　　而且，前一个数能被后一个数整除。

思路：

　　用dp[i][j]表示长度为i，最后一个数是j的序列有多少种。然后递推就可以了。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef __int64 ll;

 const ll MOD = (ll)1e9+;

 ll dp[][];

 int n, k;

 int main() {

     #ifdef Phantom01

         freopen("D.txt", "r", stdin);

     #endif // Phantom01

     while (scanf("%d%d", &k, &n)!=EOF) {

         memset(dp, , sizeof(dp));

         for (int i = ; i <= k; i++)

             dp[][i] = ;

         for (int i = ; i < n; i++) {

             for (int j = ; j <= k; j++) {

                 for (int l = j; l <= k; l += j)

                     dp[i+][l] = (dp[i+][l]+dp[i][j])%MOD;

             }

         }

         ll ans = ;

         for (int i = ; i <= k; i++)

             ans = (ans+dp[n][i])%MOD;

         printf("%d\n", (int)ans);

     }

     return ;

 }

巴特西

CF 414B Mashmokh and ACM 动态规划

最新文章

热门文章