提交记录 #309

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

#define MAX_DIGITS 1000

// 大数加法函数
void add(int *a, int *b, int *result) {
    int carry = 0;
    for (int i = 0; i < MAX_DIGITS; i++) {
        int sum = a[i] + b[i] + carry;
        result[i] = sum % 10;
        carry = sum / 10;
    }
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);

    // 检查输入是否合法
    if (a < 1 || b > 100 || a >= b) {
        printf("输入不合法\n");
        return 1;
    }

    // 初始化 dp 数组
    int dp[101][MAX_DIGITS];
    memset(dp, 0, sizeof(dp));

    // 初始化 dp[a] 和 dp[a + 1]
    dp[a][0] = 1;
    dp[a + 1][0] = 1;

    // 计算 dp 数组
    for (int i = a + 2; i <= b; i++) {
        add(dp[i - 1], dp[i - 2], dp[i]);
    }

    // 输出结果
    int start = MAX_DIGITS - 1;
    while (start > 0 && dp[b][start] == 0) {
        start--;
    }
    for (int i = start; i >= 0; i--) {
        printf("%d", dp[b][i]);
    }
    printf("\n");

    return 0;
}