题解 | #小L的多项式#

题目分析

阅读可知，题目要求的是根据每次的 求出对应的多项式 的值。

首先，先去理解这个多项式代表的含义。

也就是说计算出每一项的内容再累加求和即可。其中 的值在输入部分会得到，而 则可通过递推的方式进行求解。 ，且 我们可以从 开始不断乘 ，逐个求出 的内容。

核心框架

i64 sum=0;//总和
i64 cf=1;//x^0
for(int i=0;i<=n;i++){
    sum+=a[i]*cf;
    cf=cf*x;
}

每次查询都可通过 的复杂度求出结果， 查询，总体时间复杂度为 ​ 。

另外，由于最终结果需要取模，我们需要提升类型为 long long，并利用同余的性质，在过程中边计算边取模以避免溢出。

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1005;
const int M = 998244353;
int a[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m, x;
  cin >> n;
  for (int i = 0; i <= n; i++) {
    cin >> a[i];
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    i64 ans = 0;
    cin >> x;
    i64 cf = 1;  // x^0
    for (int j = 0; j <= n; j++) {
      ans += a[j] * cf;  // 累加每一项的内容 a[i]*x^j
      ans %= M;
      cf = cf * x % M;  // 计算x^{j+1}
    }
    cout << ans << " ";
  }
  return 0;
}