容易发现一次函数的期望是关于位置的一次函数。我们可以由此猜结论:二次函数的期望也是关于位置的二次函数。
考虑插值,一次函数实际上可以看成二次函数 \(a=0\) 的情况,因此不需要分开讨论。我们设 \(f_i(x)\) 表示第 \(i\) 轮 \(x\) 位置上的期望。注意到期望的性质,我们可以直接用上一轮的期望来推这一轮。
直接推是很难的,但注意到实际上插出一个二次函数只需要 \(3\) 个点值,我们考虑求比较好求得的 \(3\) 个: \(f_i(1),f_i(2),f_i(n)\),我们可以轻松写出如下方程:
\[f_i(1)={A_i\over n} f_{i-1}(1)+{n-A_i\over n} X_{A_i+1} \] \[f_i(2)={A_i\over n}({A_i-1\over n-1}f_{i-1}(2)+{n-A\over n-1}f_{i-1}(A_i+1))+{n-A_i\over n}({A\over n-1}f_{i-1}(1)+{n-A_i-1\over n - 1}f_{i-1}(A_i+2)) \] \[f_i(n)={A\over n} f_{i-1}(A_i)+{n-A_i\over n} f_{i-1}(n) \]这样递推过去就可以了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e7 + 5, mod = 998244353;
int x[4], y[4], ty[4], n, m, typ, inv[N];
inline int power(int a, int b) {
int t = 1, y = a, k = b;
while (k) {
if (k & 1) t = (1ll * t * y) % mod;
y = (1ll * y * y) % mod; k >>= 1;
} return t;
}
inline int la(int k) {
int ans = 0;
for (int i = 1; i <= 3; ++i) {
int del = 1;
for (int j = 1; j <= 3; ++j)
if (j != i) {
del = (1ll * del * (((k - x[j]) % mod + mod) % mod)) % mod;
del = (1ll * del * power(((x[i] - x[j]) % mod + mod) % mod, mod - 2)) % mod;
}
del = (1ll * y[i] * del) % mod;
ans = ans + del;
if (ans >= mod) ans -= mod;
} return ans;
}
#define mul(a,b) ((1ll*(a)*(b))%mod)
#define add(a,b) ((((a)+(b))%mod+mod)%mod)
int main() {
scanf("%d%d%d", &n, &m, &typ);
int A; x[1] = 1; x[2] = 2; x[3] = n;
for (int i = 1; i <= 3; ++i)
if (typ == 1) y[i] = x[i];
else y[i] = (1ll * x[i] * x[i]) % mod;
inv[1] = 1;
for (int i = 2; i < N; ++i)
inv[i] = (1ll * (mod - mod / i) * inv[mod % i]) % mod;
while (m--) {
scanf("%d", &A); if (!A || A == n) continue;
int XA = la(A), XA1 = la(A + 1), XA2 = la(A + 2), Xn = la(n);
int FA = (1ll * inv[n] * A) % mod, nFA = (1ll * (n - A) * inv[n]) % mod;
ty[1] = add(mul(FA, y[1]), mul(nFA, XA1));
ty[3] = add(mul(FA, XA), mul(nFA, Xn));
ty[2] = add(mul(FA, add(mul(mul(A - 1, inv[n - 1]), y[2]), mul(mul(n - A, inv[n - 1]), XA1))),
mul(nFA, add(mul(mul(A, inv[n - 1]), y[1]), mul(mul(n - A - 1, inv[n - 1]), XA2))));
y[1] = ty[1]; y[2] = ty[2]; y[3] = ty[3];
} int Q; scanf("%d", &Q);
while (Q--) {
int t; scanf("%d", &t);
printf("%d\n", la(t));
} return 0;
}