[UVa] 12298 - Super Poker II

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12298 - Super Poker II
Source            : UVa Online Judge
Category          : Linear Algebra
Algorithm         : Fast Fourier Transform
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long double      T;
long double              PI = acos(-1.0); // Without long double gives WA but it
                                          // cause TLE sometime
struct Complex
{
    T x, y;
    Complex(T x = 0, T y = 0) : x(x), y(y) {}
    Complex operator + (const Complex &a) const
    {
        return Complex(x + a.x, y + a.y);
    }
    Complex operator - (const Complex &a) const
    {
        return Complex(x - a.x, y - a.y);
    }
    Complex operator * (const Complex &a) const
    {
        return Complex(x*a.x - y*a.y,x*a.y + y*a.x);
    }
};
 
struct Fast_Fourier
{
    Complex A[1 << 19];
    int rev(int id, int len) // Reverse bit value 011 -> 110
    {
        int ret = 0;
        for (int i = 0; (1 << i) < len; i++)
        {
            ret <<= 1;
            if (id & (1 << i))
                ret |= 1;
        }
        return ret;
    }
    void FFT(Complex a[], int len, int DFT)
    {
        for (int i = 0; i < len; i++)
            A[rev(i, len)] = a[i];
        for (int s = 1; (1 << s) <= len; s++)
        {
            int m = (1 << s);
            Complex wm = Complex(cos(DFT*2*PI/m), sin(DFT*2*PI/m));
            for(int k = 0; k < len; k += m)
            {
                Complex w = Complex(1, 0);
                for(int j = 0; j < (m >> 1); j++)
                {
                    Complex t = w*A[k + j + (m >> 1)];
                    Complex u = A[k + j];
                    A[k + j] = u + t;
                    A[k + j + (m >> 1)] = u - t;
                    w = w*wm;
                }
            }
        }
        if(DFT == -1)
        {
            for(int i = 0; i < len; i++)
                A[i].x /= len, A[i].y /= len;
        }
        for(int i = 0; i < len; i++)
            a[i] = A[i];
        return;
    }
} fft;
 
Complex S[1<<19], H[1<<19], C[1<<19], D[1<<19];
bool vis[50005];
 
void sieve() // linear sieve
{
    int MX = 5e4 + 4;
    for (int i = 2; i*i < MX; i++)
    {
 
        if (vis[i] == 0)
        {
            for (int j = 2; i*j < MX; j++)
                vis[i*j] = 1;
        }
    }
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    sieve();
    int a, b, c;
    while (scanf("%d %d %d", &a, &b, &c) == 3)
    {
        if (a+b+c == 0)
            break;
        int len = 1;
        while (len <= b)
            len <<= 1;
        len <<= 3;
        for (int i = 0; i <= b; i++)
        {
            if (vis[i])
                S[i] = H[i] = C[i] = D[i] = Complex(1, 0);
            else
                S[i] = H[i] = C[i] = D[i] = Complex(0, 0);
        }
        for (int i = b+1; i < len; i++)
            S[i] = H[i] = C[i] = D[i] = Complex(0, 0);
        int num;
        char s;
        for (int i = 0; i < c; i++)
        {
            scanf("%d%c", &num, &s);
            if (s == 'S')
                S[num] = Complex(0, 0);
            if (s == 'H')
                H[num] = Complex(0, 0);
            if (s == 'C')
                C[num] = Complex(0, 0);
            if (s == 'D')
                D[num] = Complex(0, 0);
        }
        fft.FFT(S, len, 1);
        fft.FFT(H, len, 1);
        fft.FFT(C, len, 1);
        fft.FFT(D, len, 1);
        for (int i = 0; i < len; i++)
            S[i] = S[i] * H[i] * C[i] * D[i];
        fft.FFT(S, len, -1);
        for (int i = a; i <= b; i++)
            printf("%lld\n", (long long)(S[i].x + 0.5));
        puts("");
    }
    return 0;
}