kadai2.cpp

#include <array>
#include <iostream>

const int n = 1024;

std::array<int64_t,n> polymod(std::array<int64_t,2*n>a){
    std::array<int64_t,n> res;
    //ここに処理を書く。resに答えを入れれば良い。
    //数学的な話ではあるが、まず求めるあまりの多項式の次数は必ずn-1次以下であることがわかる。
    //よってfor文ではn-1まで回せば必ずすべての答えの配列を埋めることができる。
    //以下の説明では割られる多項式をAとする。
    //まず、x^n + 1で割るため、(Aの最大次数の項の整数係数)*(xのn-1乗)だけx^n + 1にかけて、Aからそれを引く。
    //すると、x^nに(Aの最大次数の項の整数係数)*(xのn-1乗)がかけられたものは必ず引き算によって消されるが、
    //+1*(Aの最大次数の項の整数係数)*(xのn-1乗)の項は、Aのx-1次の項の係数からAの最大次数の項の係数を引いたものが係数として残る。
    //また、Aの今出てきていない項はすべてそのままの係数で残っている。
    //これを繰り返すと容易に以下の式が成り立つことがわかると思う。(言葉で説明するのはとても難しく、いわゆる多項式の除法の筆算を想像してもらうと理解できるだろう。)
    //具体値代入->n次連立方程式->クラメルの公式や、微分なども検討したが、これが一番高速な解答であると考えられる。
    for (int i = 0; i < n; ++i) {
        res[i] = a[i] - a[i+n];
    }
    return res;
}

int main()
{
    std::array<int64_t,2*n> a;
    for (int64_t &i:a) std::cin >> i;
    std::array<int64_t,n> res;
    res = polymod(a);
    for (int64_t &i:res) std::cout << i << std::endl;
}