思路如下:
代码如下:
#include<iostream> using namespace std; const int N = 1e5 + 5; const long long MOD = 1000000007; //定义了常量 N 和 MOD。N 是数组的最大长度,MOD 是取模运算的模数。 int numsA[N], numsB[N]; //声明了两个数组 numsA 和 numsB,用于存储多项式的系数。 //读入输入数据。 int main() { int maxN, m, n; //读入 maxN 和 m,表示 numsA 数组的长度和非零项的数量。 cin >> maxN >> m; for (int i = m - 1; i >= 0; i--) cin >> numsA[i]; cin >> n; //倒序读入 numsA 数组的系数。再读入 n,表示 numsB 数组的长度,并倒序读入 numsB 数组的系数。 for (int j = n - 1; j >= 0; j--) cin >> numsB[j]; //求解多项式差的过程。 long long ret = 0, base = 1; //设置变量 ret 和 base,初始值都为 0 和 1,用于累加差值和计算权重的乘积。 int weight; for (int i = 0; i < max(m, n); i++) { weight = max(max(numsA[i], numsB[i]) + 1, 2); //遍历 numsA 和 numsB 数组中的每一项。对于每一项,计算权重为当前项的系数加 1 和 2 中的较大值, //并将其存储在 weight 变量中。 // 多项式相加取模是符合分配律的,见公式 // 这里会频繁出现越界的情况 //计算差值的部分。 ret = (ret+(numsA[i] - numsB[i]) * base)%MOD; //用 (numsA[i] - numsB[i]) * base 计算差值,并使用取模操作保持结果在合理范围内。然后,将差值累加到 ret 变量中。 base = (base*weight)%MOD; //计算下一个项的权重的乘积,并使用取模操作保持结果在合理范围内。将计算得到的值存储在 base 变量中。 } cout << ret % MOD; //输出 ret % MOD,即多项式差的结果。 return 0; }
该代码使用了取模操作,可以处理结果在整型范围内溢出的情况。同时,采用了倒序输入和遍历数组的方式,可以避免数组下标越界的问题。
加油各位!