2015年4月16日 星期四

2015/04/16 ACM-ICPC LiveArchive 2323 - Modular Multiplication of Polynomials

/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=324 */
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

struct ll
{
    #define now (*this)
    int num[2000];

    int& operator[](int x){ return num[x]; }

    ll(){ fill(num, num+2000, 0); }
    ll(int *A, int x)
    {
        now = ll();

        for(int xi = 0; xi < x; xi++)
            num[x-1-xi] = A[xi];
    }

    ll operator*(ll &p)
    {
        ll re = ll();

        for(int i = 0; i < 2000; i++)
            for(int j = 0; j < 2000; j++)
                if( now[i] && p[j] )
                {
                    re[i+j] += now[i]*p[j];
                    re[i+j] &= 1;
                }


        return re;
    }

    ll operator%(ll &p) const
    {
        ll re = now;

        int f;
        for(int i = 0; i < 2000; i++)
            if( p[i] ) f = i;

        for(int i = 2000-1; i >= 0; i--)
            if( f+i < 2000 )
            {
                if( re[f+i] )
                {
                    for(int fi = f; fi >= 0; fi--)
                        re[fi+i] ^= p[fi];
                }
            }

        return re;
    }
};

int A[2000], B[2000], C[2000];
ll a, b, c, d;
int x, y, z;

int main()
{
    int T;
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d", &x);
        for(int xi = 0; xi < x; xi++) scanf("%d", &A[xi]);
        a = ll(A, x);

        scanf("%d", &y);
        for(int yi = 0; yi < y; yi++) scanf("%d", &B[yi]);
        b = ll(B, y);

        scanf("%d", &z);
        for(int zi = 0; zi < z; zi++) scanf("%d", &C[zi]);
        c = ll(C, z);

        d = a*b%c;

        int p = 0;
        for(int di = 0; di < 2000; di++)
            if( d[di] ) p = di;

        printf("%d", p+1);

        for(int pi = p; pi >= 0; pi--)
            printf(" %d", d[pi]);

        puts("");
    }
}

沒有留言:

張貼留言