#include #include #include struct long_int { bool positive; char data[200]; }; void print_long_int(const long_int *a) { if (!a->positive) { printf("-"); } int i = 0; while (i < 199 && a->data[i] == 0) { ++i; } do { printf("%d", a->data[i++]); } while (i < 200); } int compare_long_int(const long_int *a, const long_int *b) { if (a->positive && !b->positive) { return 1; } if (!a->positive && b->positive) { return -1; } int i = 0, j = 0; while (i < 200 && a->data[i] == 0) { ++i; } while (j < 200 && b->data[j] == 0) { ++j; } if (i > j) { return a->positive ? -1 : 1; } if (i < j) { return a->positive ? 1 : -1; } if (i == j) { while (i < 200 && a->data[i] == b->data[i]) { ++i; } if (i == 200) { return 0; } return a->data[i] > b->data[j] ? (a->positive ? 1 : -1) : (a->positive ? -1 : 1); } } void read_long_int(long_int *a) { char tmp[200], c; int cnt = 0; c = getchar(); a->positive = c != '-'; if (!a->positive) { c = getchar(); } do { tmp[cnt++] = c - '0'; } while ((c = getchar()) >= '0' && c <= '9'); for (int i = 0; i < cnt; ++i) { a->data[199 - i] = tmp[cnt - 1 - i]; } } void make_long_int(long_int *a) { for (int i = 0; i < 200; ++i) { a->data[i] = 0; } a->positive = true; } void copy_long_int(long_int *res, const long_int *a) { for (int i = 0; i < 200; ++i) { res->data[i] = a->data[i]; } } void abs_long_int(long_int *res, const long_int *a) { copy_long_int(res, a); res->positive = true; } void add_long_int(long_int *res, const long_int *a, const long_int *b); void minus_long_int(long_int *res, const long_int *a, const long_int *b) { long_int tmp; char j = 0; if (!b->positive) { abs_long_int(&tmp, b); add_long_int(res, a, &tmp); } else { abs_long_int(&tmp, a); if (!a->positive) { add_long_int(res, b, &tmp); res->positive = false; } else { if (compare_long_int(a, b) == -1) { minus_long_int(res, b, a); res->positive = false; } else { for (int i = 199; i >= 0; --i) { j = 0; if (tmp.data[i] >= b->data[i]) { tmp.data[i] = tmp.data[i] - b->data[i]; } else { j = 1; while (i + j < 200 && tmp.data[i - j] == 0) { tmp.data[i - ++j] = 9; } --tmp.data[i - j]; tmp.data[i] = 10 + tmp.data[i] - b->data[i]; } } res->positive = compare_long_int(a, b) >= 0; for (int i = 0; i < 200; ++i) { res->data[i] = tmp.data[i]; } } } } } void add_long_int(long_int *res, const long_int *a, const long_int *b) { char tmp[200], x = 0; if (a->positive == b->positive) { for (int i = 199; i >= 0; --i) { tmp[i] = (a->data[i] + b->data[i] + x) % 10; x = (a->data[i] + b->data[i] + x) / 10; } for (int i = 0; i < 200; ++i) { res->data[i] = tmp[i]; } } else { long_int x; if (!a->positive) { abs_long_int(&x, a); minus_long_int(res, b, &x); } else { abs_long_int(&x, b); minus_long_int(res, a, &x); } } } int main() { int n, k; long_int *a; freopen("INPUT.TXT", "r", stdin); freopen("OUTPUT.TXT", "w", stdout); scanf("%d %d", &k, &n); a = (long_int *)malloc(sizeof(long_int) * (n + 1)); memset(a, 0, sizeof(long_int) * (n + 1)); a[n].data[199] = 1; a[n].positive = true; for (int i = n - 1; i >= 0; --i) { for (int j = 0; j < k; ++j) { if (i - j >= 0) { //a[i - j] += a[i + 1]; add_long_int(&a[i - j], &a[i - j], &a[i + 1]); } } } //printf("%d\n", a[0]); print_long_int(&a[0]); printf("\n"); free(a); return 0; }