Asking for Help: #387. BFIBONACCI

Do Xuan Hoang 2021-12-07 14:05:12 2021-12-07 14:16:49

Mọi người có thể gọi ý em cách làm tối ưu cho bài này được không ạ ? Em thử dùng bignum nhưng bị TLE mất 3 test cuối ạ.

Link đề bài

Link code của em

Tổng cộng 4 trả lời

Do Xuan Hoang

Hay quá em cảm ơn thầy ạ

Chùm CUỐI

Bài này chỉ cần cài đặt cộng số lớn bình thường. Ta tính QHĐ mảng F[] Rồi với mỗi n , ghi ra F[n] thôi. Code của bạn Đỗ Xuân Hoàng ở trên cần chú ý:

  • Tính trước mảng F[] thế này là chưa đủ, phải là 10000
for (int i = 2; i <= 5000; i++)
  • Việc cộng hai số của bạn, bạn liên tiếp cộng thêm một ký tự vào chuỗi kết quả sẽ rất chậm.

Mình sửa lại code của bạn một chút đây:

#include "bits/stdc++.h"
using namespace std;

void addBigNum(string& res, string a, string b){
	int n = max(a.length(), b.length());
    res.resize(n);
    while (a.length() < n) a = "0" + a;
    while (b.length() < n) b = "0" + b;
    int cr = 0;
    for (int i = n - 1; i >= 0; i--){
        cr += a[i] + b[i] - 48*2;
        res[i] = cr % 10 + '0';
		cr /= 10;
    }
    if (cr) res = "1" + res;
}

const int maxn = 10001;
string F[maxn];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    F[0] = "1";
    F[1] = "1";
    for (int i = 2; i < maxn; i++){
        addBigNum(F[i], F[i-1], F[i-2]);
    }
    int n;
    cin >> n;
    while (cin >> n) cout << F[n] << "\n";
}
Do Xuan Hoang

Nhân ma trận Bignum em cũng có thử nhưng cũng TLE 3 test cuối ạ Code bằng nhân ma trận Bignum

Còn tách một số lớn thành int thì nghĩa là làm như thế nào ạ :| ?

Nguyễn Hoàng Sơn

Bạn thử dùng ma trận xem, ngoài ra thì bạn cài xử lý số lớn theo số int cho nó nhanh (tức tách một số lớn thành nhiều số int)