Ural 1009. K-based Numbers

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. :-)