Codeforces 101864 M 代数数学之多项式相除

传送门:题目

题意：

有三个多项式，abc，满足 a∗b=c a ∗ b = c ，给多项式a和c的系数，让你求多项式b的各项系数

题解：

题目很简单，纯考代数数学，我当时百度了一下多项式相除公式维基百科，研究了半天终于懂了，但是写代码模拟公式很复杂，反正我没模拟出来，看了别人的代码，终于学了个简单的公式，记录如下：
我们以本题样例为例：

样例输入：
1（一组测试数组）
2（多项式a有多少项）
7 3（a： 7+3x 7 + 3 x ）
3（多项式c有多少项）
14 41 15（c： 14+41x+15x2 14 + 41 x + 15 x 2 ）

我们另a[0],a[1] ⋯⋯ ⋯ ⋯ 记作a的各项系数:a[0]=7，a[1]=3

我们另c[0],c[1] ⋯⋯ ⋯ ⋯ 记作c的各项系数:a[0]=14，a[1]=41，a[2]=15

我们先考虑

多项式乘法:

c=a∗b c = a ∗ b ，我们考虑一下c各项是怎么组成的：
易知， c[0]=a[0]∗b[0] c [ 0 ] = a [ 0 ] ∗ b [ 0 ] 因为如果a或b带x项，c一定带x所以c的常数项一定是由两个常数项相乘得到的结果。
下一步。我们考虑 c[1]=a[0]∗b[1]+a[1]∗b[0] c [ 1 ] = a [ 0 ] ∗ b [ 1 ] + a [ 1 ] ∗ b [ 0 ] ，这个也很好理解，a带x，b就不能带x，b带x，a就不能带x。
下一步。我们考虑 c[2]=a[0]∗b[2]+a[1]∗b[1]+a[2]∗b[0] c [ 2 ] = a [ 0 ] ∗ b [ 2 ] + a [ 1 ] ∗ b [ 1 ] + a [ 2 ] ∗ b [ 0 ] ，同理。
⋯⋯⋯ ⋯ ⋯ ⋯
得到通式：
c[i]=a[0]∗[bi]+a[1]∗b[i−1]+a[2]∗b[i−2]+⋯+a[i−1]∗b[1]+a[i]∗b[0] c [ i ] = a [ 0 ] ∗ [ b i ] + a [ 1 ] ∗ b [ i − 1 ] + a [ 2 ] ∗ b [ i − 2 ] + ⋯ + a [ i − 1 ] ∗ b [ 1 ] + a [ i ] ∗ b [ 0 ]

多项式除法：

因为： c[0]=a[0]∗b[0] c [ 0 ] = a [ 0 ] ∗ b [ 0 ] 。 c[0]，a[0] c [ 0 ] ， a [ 0 ] 已知，所以 b[0]=c[0]a[0] b [ 0 ] = c [ 0 ] a [ 0 ] 。
因为： c[1]=a[0]∗b[1]+a[1]∗b[0] c [ 1 ] = a [ 0 ] ∗ b [ 1 ] + a [ 1 ] ∗ b [ 0 ] 。 c[0]，a[0]，c[1]，a[1] c [ 0 ] ， a [ 0 ] ， c [ 1 ] ， a [ 1 ] 已知， b[0] b [ 0 ] 上一步已经求得，所以： b[1]=c[1]−a[1]∗b[0]a[0] b [ 1 ] = c [ 1 ] − a [ 1 ] ∗ b [ 0 ] a [ 0 ] 。
因为： c[2]=a[0]∗b[2]+a[1]∗b[1]+a[2]∗b[0] c [ 2 ] = a [ 0 ] ∗ b [ 2 ] + a [ 1 ] ∗ b [ 1 ] + a [ 2 ] ∗ b [ 0 ] 。所以： b[2]=c[2]−（a[1]∗b[1]+a[2]∗b[0]）c[0] b [ 2 ] = c [ 2 ] − （ a [ 1 ] ∗ b [ 1 ] + a [ 2 ] ∗ b [ 0 ] ） c [ 0 ]
这正是这个公式的巧妙之处：由低项式推出的结果，作为已知量往高项式递推。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define INF 0x3f3f3f3f
using namespace std;
int a[1010],b[1010],c[1010];
int main(void){
int T;
cin>>T;
while(T--){
int na,nb,nc;
cin>>na;
for(int i=0;i<na;i++)
cin>>a[i];
cin>>nc;
for(int i=0;i<nc;i++)
cin>>c[i];
nb=nc-na+1;//nb为多项式b一共有多少项
for(int i=0;i<nb;i++){
int sum=0;
for(int j=0;j<i;j++)
sum+=b[j]+a[i-j];
b[i]=(c[i]-sum)/a[0];
}
cout<<nb<<endl;
for(int i=0;i<nb;i++)
cout<<b[i]<<" n"[i==nb-1];
}
return 0;
}

最后

以上就是轻松紫菜为你收集整理的Codeforces 101864 M 代数数学之多项式相除的全部内容，希望文章能够帮你解决Codeforces 101864 M 代数数学之多项式相除所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。