когда я с длинной арифметикой сделал эту задачу я использовал в качестве основы 10000 и у меня был WA#7 тест
потом я сделал снову 10  и у меня был WA#2 тест
тогда подумав решил использовать EXTENDED всеравно WA#6 тест
кто подскажет как преодолеть 2, 6, 7 тесты

I don't understand, why did the authors create such a question that gets AC only if solved with Python or Java.

First i tried to solve this problem using int64 (long long) , i got WA6. Then i used long number theory to solve this problem and i got AC!)

Good luck!

see https://github.com/lma10h/big_int

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <bitset>
#include <stack>
#include <sstream>
#include <algorithm>

#define ll long long
using namespace std;

#define maxn 1805
#define maxk 1805

const int MAX_ONE = 1000000000;

struct x86_64 {
    int Length = 0, BigNum[1024] = {};
    x86_64(int Num = 0) {
        int Index = 0;
        while (Num) {
            BigNum[Index++] = Num % MAX_ONE;
            Num /= MAX_ONE;
        }
        Length = Index;
    }
    void operator =(int Num) {
        memset(BigNum, 0, sizeof(BigNum));
        int Index = 0;
        while (Num) {
            BigNum[Index++] = Num % MAX_ONE;
            Num /= MAX_ONE;
        }
        Length = Index;
    }
};

void print(x86_64 Num) {
    for (int i = Num.Length - 1; i >= 0; i--) {
        if (i != Num.Length - 1) {
            printf("%09d", Num.BigNum[i]);
        } else {
            printf("%d", Num.BigNum[i]);
        }
    }
}

x86_64 operator +(x86_64 A, x86_64 B) {
    int Length = max(A.Length, B.Length);
    int Carry = 0;
    x86_64 Answer;
    for (int i = 0; i < Length + 1; i++) {
        Answer.BigNum[i] = (A.BigNum[i] + B.BigNum[i] + Carry) % MAX_ONE;
        Carry = (A.BigNum[i] + B.BigNum[i] + Carry) / MAX_ONE;
    }
    Answer.Length = (Answer.BigNum[Length] == 1) + Length;
    return Answer;
}

x86_64 operator *(x86_64 A, int B) {
    int Length = A.Length;
    int Carry = 0;
    x86_64 Answer;
    for (int i = 0; i < Length + 1; i++) {
        Answer.BigNum[i] = (A.BigNum[i] * (ll)B + Carry) % MAX_ONE;
        Carry = (A.BigNum[i] * (ll)B + Carry) / MAX_ONE;
    }
    int Index = 0;
    while (Answer.BigNum[Index] != 0) {
        Index++;
    }
    Answer.Length = Index;
    return Answer;
}

x86_64 dp[maxn][2];

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    dp[1][1] = K - 1;
    for (int i = 2; i <= N; i++) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = dp[i - 1][0] + dp[i - 1][1] * (K - 1);
    }
    print(dp[N][0] + dp[N][1]);
    putchar('\n');
    return 0;
}

#include<iostream.h>
#include<stdio.h>
int main()
{
    int n,i,k;unsigned __int64 a[2000],p;
    cin>>n>>k;a[1]=k-1;a[2]=k*(k-1);
        for(i=3;i<=n;i++)
        {a[i]=(k-1)*(a[i-1]+a[i-2]);p=a[i];}
        if(n==1)
            cout<<k-1;
        else
            if(n==2)
                cout<<k*(k-1);
            else
                if(n>=3)
                    printf("%I64u", p);


    return 0;
}

Edited by author 10.04.2007 21:30

Edited by author 10.04.2007 21:31

Edited by author 10.04.2007 21:32

what's the answer when N=170 and K=10?

Why does this give runtime error #8 .
n = int(raw_input())
k = int(raw_input())
dp = [[-1 for x in xrange(15)]for y in xrange(1910)]
def solve(index,prev) :
    if(index > n ) :
        return 1
    if(dp[index][prev] != -1) :
        return dp[index][prev]
    res = 0
    start = 0
    if(index == 1) :
        start = 1
    for i in xrange(start,k) :
        if(prev == 0 and i == 0) :
            continue
        res = res + solve(index+1,i)
    dp[index][prev] = res ;
    return  res
print solve(1,0)

this is my code G++
#include<bits/stdc++.h>
using namespace std;

int n,k;


void pl(int a[],int b[],int c[])
{
  for(int i=1;i<=210;i++)
    {
    c[i]+=a[i]+b[i];
    c[i+1]+=c[i]/10;
    c[i]%=10;
  }
}

void cheng(int a[],int x)
{
  for(int i=1;i<=210;i++)
    {
    a[i]*=x;
    a[i]+=(a[i-1]/10);
    a[i-1]%=10;
  }
}

int f[2000][222];

int main()
{
    scanf("%d%d",&n,&k);
    f[0][0]=0;
    f[1][0]=1;
    f[1][1]=k-1;
    for(int i=2;i<=n;i++)
    {
        pl(f[i-2],f[i-1],f[i]);
         cheng(f[i],k-1);
    }
    for(int i=1;i<=210;i++)
    {
    f[n][i]+=f[n-1][i];
    f[n][i+1]+=f[n][i]/10;
    f[n][i]%=10;
  }
    int h=221;
    while(!f[n][h])    h--;
    for(int i=h;i>=1;i--)
        printf("%d",f[n][i]);
 return 0;
 }

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
typedef long long ll;
#define mp make_pair
const int MAXN =1500;

struct bign
{
    int len, s[MAXN];
    bign ()
    {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    bign (int num) { *this = num; }
    bign (const char *num) { *this = num; }
    bign operator = (const int num)
    {
        char s[MAXN];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    bign operator = (const char *num)
    {
        for(int i = 0; num[i] == '0'; num++) ;  //ȥǰµ¼0
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
        return *this;
    }
    bign operator + (const bign &b) const //+
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign &b)
    {
        *this = *this + b;
        return *this;
    }
    void clean()
    {
        while(len > 1 && !s[len-1]) len--;
    }
    bign operator * (const bign &b) //*
    {
        bign c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < b.len; j++)
            {
                c.s[i+j] += s[i] * b.s[j];
            }
        }
        for(int i = 0; i < c.len; i++)
        {
            c.s[i+1] += c.s[i]/10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    bign operator *= (const bign &b)
    {
        *this = *this * b;
        return *this;
    }
    bign operator - (const bign &b)
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if(i < b.len) x -= b.s[i];
            if(x >= 0) g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    bign operator -= (const bign &b)
    {
        *this = *this - b;
        return *this;
    }
    bign operator / (const bign &b)
    {
        bign c, f = 0;
        for(int i = len-1; i >= 0; i--)
        {
            f = f*10;
            f.s[0] = s[i];
            while(f >= b)
            {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.clean();
        return c;
    }
    bign operator /= (const bign &b)
    {
        *this  = *this / b;
        return *this;
    }
    bign operator % (const bign &b)
    {
        bign r = *this / b;
        r = *this - r*b;
        return r;
    }
    bign operator %= (const bign &b)
    {
        *this = *this % b;
        return *this;
    }
    bool operator < (const bign &b)
    {
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const bign &b)
    {
        if(len != b.len) return len > b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] > b.s[i];
        }
        return false;
    }
    bool operator == (const bign &b)
    {
        return !(*this > b) && !(*this < b);
    }
    bool operator != (const bign &b)
    {
        return !(*this == b);
    }
    bool operator <= (const bign &b)
    {
        return *this < b || *this == b;
    }
    bool operator >= (const bign &b)
    {
        return *this > b || *this == b;
    }
    string str() const
    {
        string res = "";
        for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
        return res;
    }
};

istream& operator >> (istream &in, bign &x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out, const bign &x)
{
    out << x.str();
    return out;
}
bign dp[1800][2];
bign k;
int n;
int main()
{
    cin>>n>>k;
    dp[0][0]=k-1;
    dp[0][1]=0;
    for(int i=1;i<n;i++){
        dp[i][0]=(k-1)*(dp[i-1][0]+dp[i-1][1]);
        dp[i][1]=dp[i-1][0];
    }
    cout<<dp[n-1][0]+dp[n-1][1];
    return 0;
}

import java.math.BigInteger;
import java.util.Scanner;

public class bigKnum {

    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();

        BigInteger f1,f2,f3;
        f1=BigInteger.valueOf(k-1);
        f2=f1.multiply(BigInteger.valueOf(k));

        for(int i=2;i<n;i++)
        {
            f3=(f1.add(f2)).multiply(BigInteger.valueOf(k-1));
            f1=f2;
            f2=f3;

        }
        System.out.print(f2);

    }

}

I compiled my code on ideone and there I have 0.4 sec for test 1800 10
So I have tle 9. Maybe there are stronger tests?
By the way my program use vectors in long arithmetics. Should I use strings in it?

Edited by author 08.05.2017 22:14

I wrote 1009 and had AC, then I added long arifmetics, changing nothing and now I have WA#1.
All test from 1009 are simmilar to 1012. What is test 1. Is it possible because of using
   stringstream out;
   out <<  k-1;
   mas[1] = out.str();
?

Use Java! :D


so... I am used to code in C++, and I'd never solved a problem in Java before. I spent like an hour learning the basics, changed all the variables in my K-based Numbers. Version 1 solution to BigInteger in Java and got AC!

The limitations were changed from 180 to 1800.

Hello problem is to find the summ of all k-based numbers?

Edited by author 30.04.2014 12:54

1) Use reccurent formula, but do no recursion,
and
2) Use BigInteger for the result

Good luck:)

#include<stdio.h>
#include<stdio.h>

void plus(char *a,char *b,char *c)
{
    char *p1,*p2,*p3;
    p1=a+99;
    p2=b+99;
    p3=c+99;
    while(*p1!=0||*p2!=0)
    {
        *p3+=*p1+*p2-2*'0';
        if(*p3>'9')
        {
            *p3-=10;
            *(p3-1)+=1;
        }
        p1--;
        p2--;
        p3--;
    }
}
void multi(unsigned char *s,int k)
{
    unsigned char *p;
    p=s+99;
    while(*p!='0')
    {
        *p+=(*p-'0')*(k-1);
        p--;
    }
    p=s+99;
    while(*p!='0')
    {
        while(*p>'9')
        {
            *p-=10;
            *(p-1)+=1;
        }
        p--;
    }
}
void main()
{
    unsigned char a[101],b[101],c[101],d[101];
    int n,k,i,j;
    for(i=0;i<100;i++)
    {
        a[i]=b[i]=c[i]=d[i]='0';
    }
    scanf("%d %d",&n,&k);
    k-=1;
    a[100]='\0';
    b[100]='\0';
    c[100]='\0';
    a[99]=k+'0';
    b[99]=(k+k*k)%10+'0';
    b[98]=(k+k*k)/10+'0';
    for(i=1;i<n-1;i++)
    {
        strcpy(c,d);
        plus(a,b,c);
        multi(c,k);
        strcpy(a,b);
        strcpy(b,c);
    }

    i=0;
    while(*(b+i)=='0')
    {
        i++;
    }
    printf("%s",b+i);

}

Is there any possible way to solve it without long arithmetics in C++? please, if yes, tell me what types should i use.

Thanks.