题意

给定多项式 $A$ 和 $C$，求 $C$ 除以 $A$ 的结果 $B$。

分析

先考虑用 $a_i$ 和 $b_j$ 表示 $c_{i+j}$，多项式乘法的朴素方法是把两式的每一位都乘起来，最后相加。

具体形式为

$$\begin{array}{c} c_{n+m}=a_{n}b_{m}\\ c_{n+m-1}=a_{n}b_{m-1}+a_{n-1}b_{m}\\ c_{n+m-2}=a_{n}b_{m-2}+a_{n-1}b_{m-1}+a_{n-2}b_{m}\\ \vdots\\ c_{0}=a_{0}b_{0} \end{array}$$

这串式子看起来没什么用，但仔细观察可以发现，其中 $a_i$ 和 $c_i$ 都是已知的，而后一个式子只比前一个多了一个未知数 $b_i$。如果我们知道 $b_{i+1}\sim b_{m}$ 的值，就可以求出 $b_{i}$。

带入式子，直接递推即可。事实上因为求的是 $B$，只需要循环到 $c_n$。

时间复杂度大概是 $O(n^2)$，可过。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll mod=1e9+7,maxn=4e5+5,maxt=505;
ll n,m,a[maxn],b[maxn],c[maxn];
inline void solve(){
    n=read(),m=read();
    for(ll i=0;i<=n;++i)a[i]=read();
    for(ll i=0;i<=n+m;++i)c[i]=read();
    for(ll i=n+m;i>=n;--i){
        ll sum=0;
        for(ll j=n-1;i-j<=m;--j){
            sum+=a[j]*b[i-j];
        }
        b[i-n]=(c[i]-sum)/a[n];
    }
    for(ll i=0;i<=m;++i)printf("%lld ",b[i]);
}
signed main(){
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}