ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1012. K-based Numbers. Version 2

Bigger=MLE Smaller=RE????
Posted by ZhaoJInsong 10 Jul 2018 08:12
#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;
}
Re: Bigger=MLE Smaller=RE????
Posted by JUSF_Patti 10 Aug 2018 09:40
my bigint struct
hope will help
const int T=400, MOD=10000000;
struct bigInt
{
int a[T], n;
bigInt(){};
bigInt(int x)
{
memset(a, 0, sizeof a);
n = 1, a[0] = x;
}
void init(int x)
{
n = 1;
a[0] = x;
}
bool operator < (const bigInt &x)
{
if (n < x.n) return 1;
else if (n > x.n) return 0;
for (int i=n-1; i>=0; i--)
if (a[i] < x.a[i]) return 1;
else if (a[i] > x.a[i]) return 0;
return 0;
}
bigInt operator * (const bigInt &x)
{
bigInt t(0); t.n = x.n + n - 1;
for (int i=0; i<n; i++)
for (int j=0; j<x.n; j++)
t.a[i+j]+=a[i]*x.a[j];
for (int i=0; i<t.n; i++)
{
t.a[i+1]+=t.a[i]/MOD;
t.a[i]%=MOD;
}
if (t.a[t.n]) t.n++;
return t;
}
bigInt operator + (const bigInt &x)
{
bigInt t(0); t.n = max(x.n, n);
for (int i=0; i<t.n; i++)
{
t.a[i] = t.a[i] + x.a[i] + a[i];
t.a[i+1]+=t.a[i]/MOD;
t.a[i]%=MOD;
}
if (t.a[t.n]) t.n++;
return t;
}
void print()
{
printf("%d",a[n-1]);
for (int i=n-2; i>=0; i--) printf("%07d",a[i]);
puts("");
}
};
Ps:this will only work with the + operator. To get AC, I changed the base from 10000 to 10000000, so the * operator won't work.