poj 1060 Modular multiplication of polynomials

àì夳堔傛蜴生んèń 2023-05-31 06:37 20阅读 0赞

> 题目衔接：[http://poj.org/problem?id=1060][http_poj.org_problem_id_1060]

> <table> 
>  <tbody> 
>   <tr> 
>    <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
>    <td>&nbsp;</td> 
>    <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
>   </tr> 
>   <tr> 
>    <td><strong>Total Submissions:</strong>&nbsp;5144</td> 
>    <td>&nbsp;</td> 
>    <td><strong>Accepted:</strong>&nbsp;2357</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> Description
> 
> Consider polynomials whose coefficients are 0 and 1. Addition of two polynomials is achieved by 'adding' the coefficients for the corresponding powers in the polynomials. The addition of coefficients is performed by addition modulo 2, i.e., (0 + 0) mod 2 = 0, (0 + 1) mod 2 = 1, (1 + 0) mod 2 = 1, and (1 + 1) mod 2 = 0. Hence, it is the same as the exclusive-or operation.  
>   
> (x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2  
>   
> Subtraction of two polynomials is done similarly. Since subtraction of coefficients is performed by subtraction modulo 2 which is also the exclusive-or operation, subtraction of polynomials is identical to addition of polynomials.  
>   
> (x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2  
>   
> Multiplication of two polynomials is done in the usual way (of course, addition of coefficients is performed by addition modulo 2).  
>   
> (x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) = x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1  
>   
> Multiplication of two polynomials f(x) and g(x) modulo a polynomial h(x) is the remainder of f(x)g(x) divided by h(x).  
>   
> (x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) modulo (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1  
> The largest exponent of a polynomial is called its degree. For example, the degree of x^7 + x^6 + 1 is 7.  
>   
> Given three polynomials f(x), g(x), and h(x), you are to write a program that computes f(x)g(x) modulo h(x).  
> We assume that the degrees of both f(x) and g(x) are less than the degree of h(x). The degree of a polynomial is less than 1000.  
>   
> Since coefficients of a polynomial are 0 or 1, a polynomial can be represented by d+1 and a bit string of length d+1, where d is the degree of the polynomial and the bit string represents the coefficients of the polynomial. For example, x^7 + x^6 + 1 can be represented by 8 1 1 0 0 0 0 0 1.
> 
> Input
> 
> The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of three lines that contain three polynomials f(x), g(x), and h(x), one per line. Each polynomial is represented as described above.
> 
> Output
> 
> The output should contain the polynomial f(x)g(x) modulo h(x), one per line.

>  Sample Input
> 
>     2 
>     7 1 0 1 0 1 1 1 
>     8 1 0 0 0 0 0 1 1 
>     9 1 0 0 0 1 1 0 1 1 
>     10 1 1 0 1 0 0 1 0 0 1 
>     12 1 1 0 1 0 0 1 1 0 0 1 0 
>     15 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1
> 
> Sample Output
> 
>     8 1 1 0 0 0 0 0 1 
>     14 1 1 0 1 1 0 0 1 1 1 0 1 0 0

>  题目大意：给你多项式的加减乘取模四种操作，现在给你三个多项式fgh现在让你求出f\*g%h
> 
> 思路；很明显这是一道多项式操作的模拟题，跟GF（2^8）有限域内的乘法类似,只不过那个模的多项式是固定的如果想有参考可以看看[传送门][Link 1]，这道题我是模拟做的，先得到两个相乘的多项式d，然后找到这个多项式的最高幂，找到相差了多少次幂，将h这个多项式整体乘上一个式子h‘，再将d-h'，反复模拟，直到多项式d的最高幂小于h即可

/*
    题目大意:
    
    思路：
    */
    #include<set>
    #include<map>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define inf 0x3f3f3f
    #define bug  printf("bug\n")
    const int maxn=1e4+10;
    const double pi=acos(-1.0);
    const double esp=1e-6;
    const int N=2e2+10;
    
    int f[maxn],g[maxn],h[maxn],a[maxn];
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            memset(a,0,sizeof(a));
            memset(f,0,sizeof(f));
            memset(g,0,sizeof(g));
            memset(h,0,sizeof(h));
            int n1,n2,n3;
            scanf("%d",&n1);
            n1-=1;
            for(int i=n1; i>=0; i--)
                scanf("%d",&f[i]);
            scanf("%d",&n2);
            n2-=1;
            for(int i=n2; i>=0; i--)
                scanf("%d",&g[i]);
            scanf("%d",&n3);
            n3-=1;
            for(int i=n3; i>=0; i--)
                scanf("%d",&h[i]);
    
            for(int i=n1; i>=0; i--)
            {
                for(int j=n2; j>=0; j--)
                {
                    if(f[i]&&g[j])
                    {
                        a[i+j]^=1;
                    }
                }
            }
            int n=n1+n2;
            while(n>=n3)
            {
                int nn=n-n3;
                for(int i=n3; i>=0; i--)
                {
                    if(h[i])
                        a[i+nn]^=1;
                }
                for(int i=n; i>=0; i--)
                {
                    if(a[i])
                    {
                        n=i;
                        break;
                    }
                }
            }
            printf("%d ",n+1);
            for(int i=n; i>=0; i--)
                printf("%d ",a[i]);
            printf("\n");
    
        }
        return 0;
    }

[http_poj.org_problem_id_1060]: http://poj.org/problem?id=1060
[Link 1]: https://blog.csdn.net/lee371042/article/details/84559042