蓝桥杯 K好数 (dp)------------C语言

2022-11-21 14:37:39 浏览数 (1)

/*问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。 求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。

输入格式 输入包含两个正整数,K和L。

输出格式 输出一个整数,表示答案对1000000007取模后的值。 样例输入 4 2 样例输出 7 数据规模与约定 对于30%的数据,KL <= 106;

对于50%的数据,K <= 16, L <= 10;

对于100%的数据,1 <= K,L <= 100。 思路:用动态规划;若求 K=4 进制 L=1 位则 有 0,1,2,3 。共4种,当L>=2时 第一位不能为0 所以 计算第一位时 把 a[1][0]=0;就是说可以 20 不可 02 可以 200,300 a[i][j]表示 以 j(0,1,2,3.。.。K-1)数 为第i位上的数字 存储的是 这种情况下的K好数 j 0 1 2 3.。。。K-1 i 1 0 1 1 1.。。。 1 2 2 2 1 2.。。。 3 5 4 3 6.。。。 。 。 。 L */

代码语言:javascript复制
#include <stdio.h>
int abs(int a)
{if(a>=0)return a;
  else return -a;
}
int main()
{long int k,l,m,i,j;
long int sum=0;
long int a[105][105]={0}; 
scanf("%ld%ld",&k,&l);
if(l>=2)
{  for(i=0;i<k;i  )// 当L==1时 所有进制内的数都可以 所以每个数都是 1个K好数 
    a[1][i]=1;
    a[1][0]=0;//第一位不能为0 

    for(i=2;i<=l;i  )
      for(j=0;j<k;j  )
       for(m=0;m<k;m  )
       {if(abs(j-m)!=1)
          a[i][j] =a[i-1][m];//a[i][j]表示第i位填 j 数字a[i-1][m]表示j可与高位那些 m 数结合 
          if(a[i][j]>1000000007)a[i][j]%=1000000007;//a[i-1][m]表示 以 m 数做低位时的 K好数数目 
       }      //a[i][j]表示 以 j 数做低位时的 K好数数目 

    }
    for(i=0;i<k;i  )
       {sum =a[l][i];
       if(sum>1000000007)sum%=1000000007;
       }

    printf("%ldn",sum);

return 0;
}
dp

0 人点赞