Bài toán VNOI: POST2

sample · August 15, 2021, 3:31pm

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?

postace · October 10, 2016, 12:30pm

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

nxphuc · October 10, 2016, 1:39pm

Với dãy A, ta tạo 1 đa thức f(x) = a₀*x⁰ + a₁*x¹ + a₂*x² + … + a₅₀₀₀₀*x⁵⁰⁰⁰⁰. Trong đó, a_i 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ó a_i*xⁱ * b_j*x^j = (a_i * b_j)*x^i+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 x^u+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 A_i + B_j = C chính bằng hệ số của x^{A_i + B_j} 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 x^C_i với C_i 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(N²), 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

tntxtnt · October 10, 2016, 1:29pm

chưa đọc, like trước cái đã

@nxphuc: rảnh thì viết lại cho đẹp đi. Muốn viết a_i+j thì viết là a<sub>i+j</sub>, muốn viết a^i+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à (a_i * b_j * x^i+j) chứ nhỉ?

nxphuc · October 10, 2016, 1:42pm

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

sample · October 10, 2016, 3:13pm

sample · October 10, 2016, 3:52pm

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

nxphuc · October 10, 2016, 4:18pm

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

tntxtnt · October 10, 2016, 5:19pm

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.

#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) << " ";
}