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?

Hai viết 02:33 ngày 01/10/2018

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

Nguyễn Xuân Phúc viết 02:25 ngày 01/10/2018
  • Với dãy A, ta tạo 1 đa thức f(x) = a0*x0 + a1*x1 + a2*x2 + … + a50000*x50000. Trong đó, ai là số lần xuất hiện của giá trị i trong mảng a.
  • Tương tự với mảng B, ta có đa thức g(x)
  • Lúc này ta thấy, khi đem 2 đa thức nhân với nhau, thì ta sẽ có 1 đa thức 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ằng u*v và đúng bằng hệ số của đơn thức trong đa thức h(x).
  • Đến đây thì ta có thể kết luận được, số cách chọn ra 2 phần tử i từ A vạ từ B sao cho Ai + Bj = C chính bằng hệ số của xAi + Bj trong đa thức 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

viết 02:35 ngày 01/10/2018

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ỉ?

Nguyễn Xuân Phúc viết 02:31 ngày 01/10/2018

đã 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 :’(

hacked viết 02:35 ngày 01/10/2018
acceptedcode.blogspot.com

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  -...

hacked viết 02:23 ngày 01/10/2018

Tiện thể cho em xin cái code FFT được không?

Nguyễn Xuân Phúc viết 02:35 ngày 01/10/2018

ủa thì trong link kia có rồi đó?

viết 02:26 ngày 01/10/2018

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>vector thôi.

#include <iostream>
#include <cmath>
#include <complex>
#include <iomanip>
#include <vector>
using namespace std;

const double pi = 3.14159265358979323846;

using Complex = complex<double>;

//http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt
vector<Complex> FFT(const vector<Complex>& A, int m, Complex w)
{
    if (m == 1) return A;
    vector<Complex> A_even(m/2);
    vector<Complex> A_odd (m/2);
    for (int i = 0; i < m; ++i)
    {
        if (i%2) A_odd [i/2] = A[i];
        else     A_even[i/2] = A[i];
    }
    auto F_even = FFT(A_even, m/2, w*w); //w^2 is a primitive m/2-th root of unity
    auto F_odd  = FFT(A_odd , m/2, w*w);
    vector<Complex> F(m);
    Complex x = 1;
    for (int j = 0; j < m/2; ++j)
    {
        F[j] = F_even[j] + x*F_odd[j];
        F[j+m/2] = F_even[j] - x*F_odd[j];
        x = x * w;
    }
    return F;
}

int main()
{
    vector<int> a{1,2,3,4,5,6,7,8,9,10};
    vector<int> b{1,2,3,4,5,6,7,8,9,10};
    int n = a.size();
    int nn = 2*n-1;
    int m = 1; while (m < nn) m *= 2;
    
    vector<Complex> A(begin(a), end(a)); A.resize(m);
    vector<Complex> B(begin(b), end(b)); B.resize(m);
    Complex w(cos(2*pi/m), sin(2*pi/m));
    
    auto F_A = FFT(A, m, w);                      // time O(n log n)
    auto F_B = FFT(B, m, w);                      // time O(n log n)
    auto F_C = F_A;
    for (int i = 0; i < m; ++i) F_C[i] *= F_B[i]; // time O(n)
    auto C = FFT(F_C, m, Complex{1}/w);           // time O(n log n)
    for (int i = 0; i < m; ++i) C[i] /= m;
    
    for (int i = 0; i < nn; ++i) cout << int(C[i].real() + 0.5) << " ";
}
Bài liên quan
0