Что не так в использовании длинной арифметики?

Question

[PRIYD]

Здравствуйте, решал задачу(условие под спойлером) и, кажется, решил правильно, но падает на 10 тесте. Насколько я понимаю, проблема в моей неправильной реализации длинной арифметики. Буду признателен за помощь.

Условие

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Входные данные
В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.

Код

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;

const ull BASE = 1e9;
const ull SIZE = 15;

vector<ull> formBI(ull num) {
	vector<ull> res(SIZE, 0);

	short i = 0;
	while (num) {
		res[i++] = num % BASE;
		num /= BASE;
	} 

	return res;
} 

vector<ull> sum(vector<ull> n1, vector<ull> n2) {
	for (size_t i=0; i<SIZE; i++) {
		n1[i] += n2[i];
	}	

	for (size_t i=0; i<SIZE-1; i++) {
		if (n1[i]>=BASE) {
			n1[i] -= BASE;
			n1[i+1]++;
		}
	}
	
	return n1;
}

void print(vector<ull> n) {
	reverse(n.begin(), n.end());

	for(size_t i=0; i<SIZE; i++) {
		if (n[i]!=0) {
			cout << n[i];
		}
	}	

	cout << endl;
}

int main() {
	short k, n;
	cin >> k >> n;
	
	vector<ull> emp(SIZE, 0);
	vector<vector<ull>> b(n+1, emp); 
	b[0] = formBI(1);
	
	for (size_t i=1; i<n+1; i++) {
		short r = (i<k) ? i : k;
		
		for (size_t j=1; j<=r; j++) {
			b[i] = sum(b[i], b[i-j]);
		}
	}

	print(b[n]);
	return 0;
}

Answer 1

[Wataru]

Проблема в выводе. Вы нулевые цифры вообще не выводите:

for(size_t i=0; i<SIZE; i++) {
  if (n[i]!=0) {
    cout << n[i];
  }
}

А нужно пропускать только ведущие нули. Самый простой способ исправить - завести bool printed:

bool printed = false;
for(size_t i=0; i<SIZE; i++) {
  if (printed || n[i]!=0) {
    cout << n[i];
    printed = true;
  }
}

Ну, еще может быть стоит увеличить размер длинных чисел. Не факт, что 135 цифр хватит. Введите тест n=300, k=300, и проверьте что выводится один и тот же ответ при текущем и увеличенном SIZE.

Comments

[xmoonlight]

Мне кажется, что без циклов проще формулу комбинаций вывести...
Как думаешь?

[Wataru]

xmoonlight, Нет, тут нет простой комбинаторной формулы. Если бы не было ограничения на размер слагаемых, то ответ был бы 2^n, Если k=2, то ответ - n-ое число фиббоначи. Для произвольного k тут некое обобщение чисел фиббоначи. Простой и замкнутой формулы тут нет. Можно, конечно, иррациональные корни характеристического многочлена возводить в степень, как золотое сечение для чисел фиббоначи, но это применимо только для маленьких k, да и это решение будет гораздо сложнее при реализации, ведь тут нужна точность в сотни знаков. Это значит, надо вместо сложения BigInt-ов реализовывать произведения, деления, корни для чисел с фиксированной точкой.

[xmoonlight]

Илья Николаевский, Понял. Попробую решить задачку. Отпишусь.

[Wataru]

xmoonlight, Для очень больших n, но маленьких k можно применить трюк с возведением матрицы в степень. Это будет O(k^3 log n) вместо O(kn), Но умножений BigInt-ов, а не сложений. В приведенных в задаче ограничениях это не имеет смысла.