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

WRONG ANSWER ON TEST #3???
Posted by the114514 21 Apr 2022 18:36
#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;
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;
}

x86_64 operator *(x86_64 A, int B) {
int Length = A.Length;
int Carry = 0;
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++;
}
}

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;
}