自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:11:56，当前版本为作者最后更新于2019-09-12 16:45:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人： 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

将询问离线，问题转化为：

1. 加入一个点值。

2. 设当前点值集合大小为 $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;
}