算法训练 K好数 (DP)
2023-09-11 14:22:48 时间
问题描述
如果一个自然数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。
题解:
状态转移方程:dp[i][j] = dp[i][j] + dp[i-1][t] //其中dp[i][j]表示一共有两位数字,首位为j时的方法数。
AC代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<stdio.h> #include<math.h> #include<algorithm> #include<string.h> const int MOD = 1000000007; using namespace std; int main() { int k, l; //k进制,长度为l int dp[200][200]; //dp[i][j]表示一共有i位数字,首位为j long long ans; while(scanf("%d%d", &k,&l) != EOF) { ans = 0; memset(dp, 0, sizeof(dp)); for(int i = 0; i < k; i++) dp[1][i] = 1; for(int i = 2; i <= l; i++) //位数 { for(int j = 0; j < k; j++) //首位 { for(int t = 0; t < k; t++) { if(abs(t-j) != 1) //判断相邻两位是否相邻 dp[i][j] = (dp[i][j] + dp[i-1][t]) % MOD; } } } for(int i = 1; i < k; i++) ans = (ans + dp[l][i]) % MOD; printf("%lld\n", ans); } return 0; }
相关文章
- 计算机等级考试二级C语言程序设计专项训练题——单链表
- 自动混合精度训练
- (《机器学习》完整版系列)第5章 神经网络——5.3 SOW网络(“灯阵”面板)、Elman网络(将训练集转化时序数据)、Boltzmann机(达到Boltzmann分布)
- [DeeplearningAI笔记]第二章1.1-1.3偏差/方差/欠拟合/过拟合/训练集/验证集/测试集
- 【UWB系统同步】OFDM基于训练序列的同步算法的MATLAB仿真
- 采用tfrecord形式读写训练数据
- 蓝桥杯练习系统 【试题】【算法训练】 礼物
- YOLOV5学习笔记(二)——环境安装+运行+训练
- 基于浅层神经网络(全连接网络)的强化学习算法(Reinforce) 在训练过程中出现梯度衰退(degenerate)的现象
- 【PyTorch教程】06-如何使用PyTorch搭建神经网络模型并进行训练
- 算法训练 区间k大数查询
- 算法训练 矩阵乘法
- 算法训练 5-1最小公倍数
- 蓝桥杯 之 算法训练 排序
- 蓝桥杯训练3
- 算法训练 Pollution Solution(计算几何)