01/10/2018, 00:23
Bài toán VNOI: POST2
Links bài toán: http://vnoi.info/problems/show/POST2/
Nghe bảo là thuật toán FFT gì đó? Có anh chị nào giúp em với?
Bài liên quan
Links bài toán: http://vnoi.info/problems/show/POST2/
Nghe bảo là thuật toán FFT gì đó? Có anh chị nào giúp em với?
Chưa code mà chỉ phân tích đề 1 chút, bài này mình chỉ giải được với độ phức tạp O(n^2) thôi
i
trong mảng a.g(x)
h(x)
mới. Trong đó ta có ai*xi * bj*xj = (ai * bj)*xi+j. Đến đây ta thấy có sực đặc biệt, đó là nếu xét trên 2 mảng A, B ban đầu, số cách tạo ra tổng (x+y) với x là phần tử thuộc A và y là phần tử thuộc B sẽ bằng số lần xuất hiện của x trong A nhân với số lần xuất hiện của y trong B. Nếu tạo ra đơn thức tương tự như ở trên, thì rõ ràng lúc này ta có hệ số của xu+v đúng bằngu*v
và đúng bằng hệ số của đơn thức trong đa thứch(x)
.h(x)
.Như vậy thì nếu ta tính được tich 2 đa thức f(x)*g(x) từ 2 mảng A và B, thì kết quả của bài toán cần tìm là tổng hệ số của xCi với Ci là các phần tử của mảng C.
Thì nếu tính nhân đa thức bình thường sẽ có đpt là O(N2), không đủ nhanh để Accept bài này, thì ta cần 1 thuật toán nhanh hơn, đó là FFT với đpt O(NlogN).
Trên đây là mình chứng minh vì sao dùng FFT, còn source FFT và lý thuyết FFT thì bạn tìm hiểu thêm nhé. Mà thực tế thì chỉ cần hiểu FFT là gì, FFT dùng để làm gì, dùng khi nào, và làm sao chuyển bài toán về đa thức để làm FFT là được, rồi tìm 1 source chất lượng lưu lại đó, sau này gặp bài FFT là đưa vào xài thôi. Chứ source FFT có thể nói là cố định, không nên thay đổi lung tung (cũng giống như các dạng bài về luồng cực đại (Max Flow) hay cặp ghép cực đại (Maximal Matching)), đều là đưa bài toán về dạng đó và áp dụng code, chứ không biến đổi code theo đề bài.
p/s: dân tự nhiên ngu văn, viết dài dòng thông cảm :3
chưa đọc, like trước cái đã
@nxphuc: rảnh thì viết lại cho đẹp đi. Muốn viết ai+j thì viết là
a<sub>i+j</sub>
, muốn viết ai+j thì viết làa<sup>i+j</sup>
a_i*x^i * b_j*x^j = (a_i + b_j)*x^(i+j)
phải ra là (ai * bj * xi+j) chứ nhỉ?đã fix, thanks
tìm hoài không thấy mấy cái superscript với subscript này, ra là phải gõ tay từ cái :’(
POST2 - A cộng B version 2
Cho 3 dãy N số nguyên A1, A2, ..., An, B1, B2, ..., Bn và C1, C2, ..., Cn. Hãy đếm số bộ 3 (Ai,Bj,Ck) thỏa mãn Ai + Bj = Ck. Input -...
Tiện thể cho em xin cái code FFT được không?
ủa thì trong link kia có rồi đó?
http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt
http://rextester.com/XJULV18846 code từ cái trang trên nè. Xài
complex<double>
vàvector
thôi.