提供邵阳网站建设,网页设计考试,印刷报价网站源码下载,企业管理系统开源问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字#xff0c;那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K 4#xff0c;L 2的时候#xff0c;所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大#xff0c;请你输出… 问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K 4L 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。 题意就是 需要在L长度下的K进制数 相邻位处的数字绝对值之差不可为1 求满足这样条件的数有多少个
一开始用搜索做 果断超时
后来发现其实在以i长度下的数串下以j为结尾的数串的数目 就是 在i-1长度下 除了与j绝对值差值为1的数字结尾的所有可能的加和
dp[i][j] dp[i-1][m];m为与j不相邻的数 #includebits/stdc.h
using namespace std;
typedef long long ll;
int dp[110][110];
const int MOD 1000000007;
int main()
{int k,l;cinkl;for(int i0;ik;i)dp[1][i]1;for(int i2;il;i){for(int j0;jk;j){for(int m0;mk;m){if(abs(m-j)!1){dp[i][j]dp[i-1][m];dp[i][j]%MOD;}}}}ll sum0;for(int i1;ik;i){sumdp[l][i]; sum%MOD;}coutsum%MODendl;return 0;
}
