Thank you very much!
With your help,I get AC now!

Thanks a lot,at the first time I want decrease the cost of memory so I used each four digits to represent one digit，but this compression also take the number a mistake，when it should get an output for 0146，the program output an 146，it lost some digits~~~~~

THX！

No, your 'dimamic program' shouldn't 'word' because you have to use big numbers...


Edited by author 23.03.2005 06:42

You are wrong.

"k-based number" means "K进制数"
"successful zeroes" means "连续的零"

Thank you for help. I understand my mistake.

You know long arithmetic? This problem solved usin it.

Use long arithmetic and algorithm 1009 :)))

Because you are very ugly!
                ~~~~

Edited by author 21.07.2007 16:48

 Your logic seems OK (I didn't check it, but it seems). Your problem
is that the numbers might (and will) be bigger than a longint (not in
the input but in the output).

Quote:
"You may assume that 2 <= K <= 10; 2 <= N; 4 <= N+K <= 180."

This means you have to use BIG numbers!

you can use an array of integers for that huge number . when
n = 1800 and k = 10 the answer have about 3600 digits !!! and
you cant store it in nor long nor any other variable.
in this problem you must find a recursive relations . ( not to
consider all answer ). it has a nice soloution . if you use
this method but not receive the correct answer mail me at :
ioi_khafan@hotmail.com . thanks . bye

b[i]*int may be more than MaxLongInt

Just look at my page:
acmsolver.timus.ru
There is a description how to solve it.
SAV

u can use a cycle instead of recursion.
and the change array (int)ways[200] into (int)ways[3][2000]; because the result will has maore than 100 digits, mathematic arithmetic is needed. i change you programme as follow:

//dynamic programming

#include <iostream.h>
#include <stdio.h>
int ways[3][20000]={0};
int ADD(int a[], int b[], int c[]);
int MUL(int a[], int k);
int main()
{
    long n, k, i, j;
    cin>>n>>k;
    ways[0][1] = 1;
    ways[0][0] = 1;
    ways[1][1] = k-1;
    ways[1][0] = 1;
    for (i=2; i<=n; i++)
    {
         ADD(ways[2], ways[1], ways[0]);
        MUL(ways[2], k-1);
        j = 2;
        i++;
        if (i>n)
            break;
        ADD(ways[0], ways[2], ways[1]);
        MUL(ways[0], k-1);
        j = 0;
        i++;
        if (i>n)
            break;
        ADD(ways[1], ways[0], ways[2]);
        MUL(ways[1], k-1);
        j = 1;
    }
    for (i=ways[j][0]; i>=1; i--)
    {
        cout<<ways[j][i];
    }
    return 0;
}

int ADD(int a[], int b[], int c[])
{
    int i, remainder, carry;
    for (i=1, carry=0; i<=b[0] && i<=c[0]; i++)
    {
        remainder = (b[i] + c[i] + carry) % 10;
        carry = (b[i] + c[i] + carry) / 10;
        a[i] = remainder;
    }
    for (; i<=b[0]; i++)
    {
        remainder = (b[i] + carry) % 10;
        carry = (b[i] + carry) / 10;
        a[i] = remainder;
    }
    for (; i<=c[0]; i++)
    {
        remainder = (c[i] + carry) % 10;
        carry = (c[i] + carry) / 10;
        a[i] = remainder;
    }
    if (carry==1)
    {
        a[i++] = carry;
    }
    a[0] = i - 1;
    return 0;
}

int MUL(int a[], int k)
{
    int i, remainder, carry=0;
    for (i=1; i<=a[0]; i++)
    {
        remainder = (a[i] * k + carry) % 10;
        carry = (a[i] * k + carry) / 10;
        a[i] = remainder;
    }
    for (; carry>0; i++)
    {
        remainder = carry % 10;
        carry = carry / 10;
        a[i] = remainder;
    }
    a[0] = i - 1;
    return 0;
}