首页 > 代码库 > 第一轮 I
第一轮 I
K-based NumbersTime Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uSubmit StatusDescriptionLet’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example: 1010230 is a valid 7-digit number; 1000198 is not a valid number; 0001235 is not a 7-digit number, it is a 4-digit number. Given two numbers N and K, you are to calculate an amount of valid K based numbers, containing N digits.You may assume that 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.InputThe numbers N and K in decimal notation separated by the line break.OutputThe result in decimal notation.Sample Inputinput output210 90/************************************************************************* > File Name: i.cpp > Author:yuan > Mail: > Created Time: 2014年11月09日 星期日 21时52分04秒 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; long long ans[2][20]; int n,k; int main() { cin>>n>>k; memset(ans,0,sizeof(ans)); ans[0][1]=0;ans[1][1]=k-1;/*分别指定了长度为1,末尾数字为0的个数为0,不为的个数为k-1*/ for(int i=2;i<=n;i++) { ans[0][i]=ans[1][i-1];/*不能出现连续的0,则长度为n末尾为0的个数等于长度为n-1末尾不为0的个数*/ ans[1][i]=(k-1)*(ans[0][i-1]+ans[1][i-1]);/*长度为n,末尾数字不为0的个数:末尾数字可以是1—k-1中的任意一个 倒数第二位可以为0,也可以不为0*/ } cout<<ans[0][n]+ans[1][n]<<endl; return 0; }
第一轮 I
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。