ABC137 F 题解
Link
说在前面：SB deepseek告诉我this的导数为 \(-1\)。
思路
跟Lagrange差不多，就是构造一个“开关函数”：对于 \(x=x_i\)，\(g_i(x)=1\)，否则等于 \(0\)。
那么这道题又是在 \(\mathbb{F}_p\) 域上，模 \(p\) 意义下。考虑使用 Fermat 小定理。
对于任意整数，有 \(x^{p-1}=1\)。那么令 \(g_{i}(x)=1-(x-i)^{p-1}\)。
即，在 \(x=i\) 时，\(g_{i}(x)=1\)，否则等于 \(0\)。
所以题目所求 ：
\[\begin{aligned}f(x)&=\sum\limits_{i=0}^{p-1}\sum\limits_{j=0}^{p-1}a_jg_{i}(x)\\
\end{aligned}\]
然后直接拆开求值即可。
代码
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 3005;
int a[N], n;
ll fac[N], rev[N], ans[N];
ll qpow(ll a, ll b) {ll ret = 1;while (b) {if (b & 1) ret = (ret * a) % n;a = (a * a) % n;b >>= 1;}return ret;
}
void init(void) {fac[0] = rev[0] = 1;for (int i = 1; i < N; ++i) {fac[i] = (fac[i - 1] * i) % n;rev[i] = (rev[i - 1] * qpow(i, n - 2)) % n;}
}
ll C(int a, int b) {if (a < b) return 0;return fac[a] * rev[b] % n * rev[a - b] % n;
}
int main() {FASTIO;cin >> n;init();for (int i = 0; i <= n - 1; ++i) {cin >> a[i];ll add = (a[i] - a[i] * qpow(i, n - 1) % n) % n;add = (add + n) % n;ans[0] = (ans[0] + add) % n;}for (int i = 1; i <= n - 1; ++i) {for (int j = 0; j <= n - 1; ++j) {ll add = (C(n - 1, i) * qpow(n - j, n - 1 - i) % n * a[j] % n) % n;add = (n - add) % n;ans[i] = (ans[i] + add) % n;}}for (int i = 0; i <= n - 1; ++i)cout << ans[i] << ' ';return 0;
}