#include<stdio.h>
int power(const int a,const int b)
{
    int k=0,num=1;
    for(k=0;k<b;k++)
    {
        num=num*a;
    }
    return num;
}
int foc(int a)
{
    if(a==1)
    {
        return 1;
    }
    else
    {
        return foc(a-1)*a;
    }
}
int arr(int a,int b)
{
    if(!b)
    {
        return 1;
    }
    else
    {
        return foc(a+b)/(foc(a)*foc(b));
    }
}
int main(void)
{
    int n=0,k=0,i=0,sum=0;
    scanf("%d",&n);
    scanf("%d",&k);
    for(i=0;n-i>=i;i++)
    {
        if(!i)
        {
            sum=sum+power(k-1,n);
        }
        else if(i==1)
        {
            sum=sum+(n-1)*power(k-1,n-1);
        }
        else
        {
            sum=sum+arr(i,n-2*i)*power(k-1,n-i);
        }
    }
    printf("%d\n",sum);
    return 0;
}
test results:
N   K  result
3   10   891
4   10   8829
5   10   87480
6   10   866781
7   10   8588349
8   10   85096170
2   2    2
3   8    441
5   9    50688

I'll appreciate it if you find the dead test and point my bug out,thank you!
By the way,I get the WA at test#2.

Edited by author 16.11.2010 20:38

import java.util.Scanner;
import java.util.Arrays;
public class T_1009 {
    public static void main(String[] args)
    {
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int k = sc.nextInt();
         int[] m = new int[n+1];
         // Dynamic
         m[1] = k-1;
         m[2] = k*(k-1);
         for (int i = 3; i <=n; i++)
        {
            m[i] = (m[i-1]+m[i-2])*(k-1);
        }
           System.out.print(m[n]);
    }
}

for k = 2, n = 2 Enigma [UB of TUIT] programm write 3, but right answer 2, because:
10
11