新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
問題 
係数が0か1しかない多項式を考える。2つの多項式の加算は、次数が等しい項の係数同士の加算によって実現される。係数同士の加算は mod 2 の加算により行われる。すなわち、(0 + 0)mod 2 = 0, (0 + 1)mod 2 = 1, (1 + 0)mod 2 = 1, (1 + 1)mod 2 = 0 である。これは排他的論理和の演算と等価である。
(x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2
2つの多項式の減算も同じように行われる。係数同士の減算も mod 2 の減算で行われ、この演算も排他的論理和の演算と等価であるので、多項式同士の減算は加算と同じである。
(x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2
2つの多項式の乗算は、普通の多項式と同じように行われる。(もちろん、係数同士の加算は、mod 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
(2つの多項式 f(x)とg(x)の積) modulo (多項式 h(x)) は、f(x)g(x)を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
その多項式中でもっとも大きい次数を、その式の次数とする。例えば、x^7 + x^6 + 1 の次数は7である。
あなたは、3つの多項式f(x), g(x), h(x)が与えられたときに、f(x)g(x) modulo h(x)を計算するプログラムを作成する。f(x)とg(x)の次数はh(x)の次数より小さいことが保証されている。多項式の次数は1000より小さい。
多項式の係数は0か1であることから、多項式はその次数をdとして、整数d+1と、続くd+1個の0か1の文字で表される。0か1の文字は、多項式の係数を表している。例えば、x^7 + x^6 + 1は、8 1 1 0 0 0 0 0 1と表せる。
入力
この入力はT個のテストケースから成る。テストケースの数Tは、入力の1行目に与えられる。各テストケースは3行からなり、それぞれの行が多項式f(x), g(x), h(x)を表している。各多項式は上に書いたように表されている。
出力
それぞれのテストケースについて1行ずつ、多項式 f(x)g(x) modulo h(x) を出力する。
入力の例
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
出力の例
8 1 1 0 0 0 0 0 1 14 1 1 0 1 1 0 0 1 1 1 0 1 0 0
出典
Taejon 2001
