1009. K-based Numbers
Time Limit: 1.0 second
Memory Limit: 16 MB
Let’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.
Input
The numbers N and K in decimal notation separated by the line break.
Output
The result in decimal notation.
Sample
input output
2
10
90
题目大意:给定一个正整数k和n( 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18),试确定K进制的N位数且没有连续的两个0及没有前导0。
算法分析:此题是Fibonacci数列的变形题。设f(n)表示符合题目条件的n位K进制的数的总数。则有:f(n)=(k-1)*(f(n-1)+f(n-2)),且f(1)=k-1,f(2)=k*(k-1)
注意:当n==1时,直接输出k,进行特判!
#include <iostream>
using namespace std;
typedef long long lld;
const int maxn=20;
int main()
{
lld f[maxn];
lld n,k;
cin>>n>>k;
if(n==1) {cout<<k<<endl;return 0;}//特判n=1的情况
f[1]=k-1;
f[2]=k*(k-1);
for(lld i=3;i<=n;i++)
{
f[i]=(f[i-1]+f[i-2])*(k-1);
}
cout<<f[n]<<endl;
return 0;
}
附:时间复杂度O(logn)及空间复杂度为O(1)的算法:
Sure, you're welcome.
Okay, we're already know, that the answer can be found reccurently: F(N) = (K-1)*(F(K-1)+F(N-2)), where F(0) = 1, F(1) = K-1. We see, that the {F(N)} sequence is very similar to Fibonacci's one and can assume some facts. I see two different approaches to solve the problem.
1) First way is to build characteristic equation, solve it and get an exact formula for F(N). I didn't try this way, because I foresaw some problems with precision and float calculations. If you're interested, you can turn to this article as a manual:
http://www.intuit.ru/department/algorithms/algocombi/8/2.html
2) I assumed, that method with fast matrix exponentiation will work as well as for Fibonacci's numbers.
Just consider a matrix: L(N) = {{F(N+1), F(N)}, {F(N), F(N-1)}}.
Let's try to find such R, that L(N)*R = L(N+1).
If you write down this information, you'll easily see, that R = {{K-1, 1}, {K-1, 0}}. So all you need is to find L(1)*R.pow(N-2).
Hope this information was helpful, I'm not sure it is the best way to describe an approach though. :-)
分享到:
相关推荐
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
语言:русский 在网站上的联合购买的扩展59.rf shopping59.rf - 这是烫发中的一个联合...ural-toys.ru。我们还接受来自其他网站的订单:odezhda-master.ru。gepur.com.ua。milofo.ru。z29.ru.Butik-duhov.ru
在Shopping59.rf网站上进行联合购物扩张 Shopping59.RF - 这是在彼尔姆联合...ural-toys.ru 我们也接受来自其他网站的订单: odezhda-master.ru gepur.com.ua milofo.ru z29.ru butik-duhov.ru 支持语言:русский
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
资源分类:Python库 所属语言:Python 资源全名:ural-0.25.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
Pascal acm_timus_ural_1148.pas
Ural
URAL-PHA
URAL3D
Pascal acm_timus_ural_1099.pas
URAL(Timus Online Judge)部分测试数据 不全
Philip_Dural_UX-UI_Designer:UXUI设计器配置文件
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
Thanks to the National Nat- ural Science Foundation (61033013, 60775045, 61672364, 61672365), Soochow scholar program (14317360, 58320007) and the key subjects of Jiangsu province “Technology of ...
Comprising the westernmost peninsula of Eurasia, Europe is generally 'divided' from Asia to its east by the watershed divides of the Ural and Caucasus Mountains, the Ural River, the Caspian and Black...
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路