蓝桥杯题目-可构造的序列总数

链接

可构造的序列总数 - 蓝桥云课 (lanqiao.cn)

知识点

动态规划

思路

        定义表示序列长度为,以结尾的合法序列的数量 ，初始化时有 。因为题意要求  是 的倍数，所以在转移时每个数应该从它的因子转移过来，即:

                                        dp[i][j]=dp[i][j]+dp[i-1][j的因数]

代码

#include <bits/stdc++.h>
using namespace std;

const int N=2005;
const int mod=1e9+7;
long long dp[N][N]; //dp[i][j]表示序列长度为i,以j结尾的合法序列的数量 

int main()
{
  int n,k;
  cin>>k>>n;
  for(int i=1;i<=k;i++){
    dp[1][i]=1;  //只有一个数的时候每一个都只能选自己
  }
  
  //以9举例子：
  //dp[i][9]=dp[i-1][1]+dp[i-1][3]+dp[i-1][9]
  
  for(int i = 2;i <= n; i++){  //序列长度的取值
    for(int j = 1;j <= k; j++){ //枚举序列中最大的那个数
      for(int t = 1;t <= sqrt(j); t++){ //这个是枚举那个数是可以的
        if(t == sqrt(j)){  //刚好是j的平方根的时候只有一个数
          dp[i][j] = (dp[i][j] + dp[i-1][t]) % mod;
        }
        else if(j % t == 0){ //当前的数是因子
        
          dp[i][j] = (dp[i][j] + dp[i-1][t] + dp[i-1][j/t]) % mod;
          //把是因数的都加起来  当j%t==0的时候会有两个因数成立的
        }
      }
    } 
  }
  
  long long ans=0;
  for(int i = 1;i <= k; i++){  //对序列长度为n符合序列进行求和
    ans=(ans + dp[n][i]) % mod;  //序列长度是n的以i为最大的那个数的和
  }
  cout<<ans;
  return 0;
}