Yukicoder040 多項式の割り算

問題概要

与えられた多項式$A[D]*x^D+A[D-1]*x^{D-1}+…+A[1]*x+A[0]$
を $x^3−x$ で割った余りを出力してください。

$0\leqq D\leqq10^4$、$-10^2\leqq A[i]\leqq10^2$

yukicoder040

解法

解法1:多項式の割り算の筆算をそのまま書く。$O(N)$
解法2:$(与式) = Q(x)(x+1)x(x-1) + ax^2 + bx + c$
なので、$x=1,0,-1$を代入して連立方程式を解く。$O(NlogD)$

計算量:$O(N)$ or $O(NlogD)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI a(N + 1);
        FOR(i, 0, N + 1) {
            cin >> a[i];
        }
        FORR(i, N, 3 - 1) {
            a[i - 2] += a[i];
            a[i] = 0;
        }
    
        int idx = 2;
        while (idx&&a[idx] == 0)idx--;
    
        cout << idx << endl;
        FOR(i, 0, idx + 1) {
            cout << a[i] << " \n"[i == idx];
        }
    
        return 0;
    }