题解 P5553 【电学实验】
hsfzLZH1
·
·
题解
出题人： hsfzLZH1
本题主要考察数学知识和各种乱搞能力。
题目大意
给出一个最高 n-1 次的多项式 f(x) ，对于 i\in \mathbb{Z} 且 1\le i\le n ，有 f(x)=x^{-1} ~ (\mod 998244353) ，求 f(n+1)\mod 998244343 的值。
10pts
直接计算打表即可。
30pts
当然可以打出更大的表。
设 f(x)=\sum_{i=0}^{n-1} a_i x^i ，即将点值表示法转化为系数表示法，然后带入 x=n+1 求出值。
分别令 x=1,2,\ldots , n ，可以得到 n 条以 a_i 为变量的多元一次方程，用 高斯消元 求解即可求出 a_i 。时间复杂度 O(Tn^3) 。
当然，也可以对每组数据进行一次 拉格朗日插值 ，根据 n 个点值插出另一个点值，时间复杂度 O(Tn^2) 。
每次对相邻两个数进行差分，对差分数组再次进行差分，直到只剩下一个数，按这个数进行差分的逆运算，也可以求出 f(n+1) 的值，时间复杂度 O(Tn^2) 。
50pts
将询问离线，问题转化为：
-
加入一个点值。
-
设当前点值集合大小为 s ，求出这 s 个点对应的 s-1 次多项式在某一处的值。
这个问题可以在预处理后单次操作 O(s) 解决。
当然，将询问离线后，也可以在上次差分的基础上进行差分，单次也是 O(n) 的。
时间复杂度 O(n^2+T) 。
70pts
观察到本题给出的是在 1,2,\ldots ,n 时的点值，这样的插值可以在 O(n) 时间复杂度内解决的。时间复杂度 O(Tn) 。
不知道有没有用分治 FFT 的 O(n\log_2 n) 做法。
100pts
先考虑在什么时候会出现逆元未定义或不存在这样的多项式的情况，当 n\ge 998244353 时，会出现逆元未定义的情况，而当 n< 998244353 时，因为给出的点值均不相同，所以一定存在这样的多项式。
开始愉快地推式子：
根据拉格朗日插值的式子， f(x)=\sum_{i=1}^n y_i \prod_{j\neq i} \dfrac {x-x_j} {x_i-x_j}
令 x=n+1,x_i=i,y_i=\dfrac 1 i ，有 f(n+1)=\sum_{i=1}^{n} \dfrac 1 i \prod_{1\le j\le n,j\neq i} \dfrac {n-j+1} {i-j}
f(n+1)=\sum_{i=1}^n \dfrac {\prod_{1\le j\le n,j\neq i}(n-j+1)} {\prod_{0\le j\le n,j\neq i} {i-j} }
f(n+1)=\sum_{i=1}^n \dfrac {(-1)^{n-i}n!} {(n-i+1)(n-i)!i!}
f(n+1)=\dfrac 1 {n+1} \sum_{i=1}^n (-1)^{n-i} \dfrac {(n+1)!} {(n-i+1)!i!}
f(n+1)=\dfrac 1 {n+1} \sum_{i=1}^n (-1)^{n-i} C_{n+1}^{i}
f(n+1)=\dfrac 1 {n+1} (-(-1)^n C_{n+1}^0 -(-1)^{-1} C_{n+1}^{n+1}+\sum_{i=0}^{n+1} (-1)^{n-i}C_{n+1}^i)
\sum_{i=0}^{n+1} (-1)^{n-i}C_{n+1}^i=-(1-1)^{n+1}=0
f(n+1)=\dfrac {1-(-1)^n} {n+1}
所以， n 是偶数时， f(n+1)=0 ； n 是奇数时， f(n+1)=\dfrac 2 {n+1} 。（这个规律应该打表也能找得出来）
参考代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll T,n;
ll ksm(ll a,ll k)
{
ll ret=1,x=a%mod;
while(k)
{
if(k&1)ret=ret*x%mod;
x=x*x%mod;k>>=1;
}
return ret;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
if(n>=mod)printf("-1\n");
else if(n&1)printf("%lld\n",2*ksm(n+1,mod-2)%mod);
else printf("0\n");
}
return 0;
}