nowcoder 181045 / 克洛涅的多项式构造+思维

题意：有多项式 $F(x),G(x)$，最高次项分别为 $n,m$。$F(x)$ 最高次项系数为 $1$. $m<n$

给定 $n$ 个不同的点值，满足 $F(x[i])=G(x[i])$

给定多项式 $G(x)$，求 $F(k)$，$k$ 是给定的.

我们知道，$i+1$ 个不同的坐标能确定一个 $i$ 次多项式，即只要有 $i+1$ 个不同的坐标是确定的，那么这个多项式也就确定了.

题中给定了 $n$ 个时刻的横坐标，即 $F(x)=G(x)$，那么有 $F(x)-G(x)=0$.

令 $n$ 次多项式 $M(x)=F(x)-G(x)$

而 $M$ 一定可以被表示成 $0$ 点式，即 $(x-a)(x-b)(x-c)......(x-n)$ 即一共有 $n$ 项.

根据上面的性质：$n+1$ 个点确定唯一的一个多项式，而上面的 $0$ 点式只需 $n$ 个点，所以 $M(x)$ 可以被确定.

而 $G(x)+M(x)=F(x)$

所以在这个式子中，$M(x)$ 被 0 点式确定，而 $G(x)$ 是给定的，所以直接将 $k$ 带入求值即可.

#include <bits/stdc++.h>

#define ll long long

#define mod 998244353

#define N 1000006

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

namespace IO

{

	char *p1, *p2, buf[100000];

	#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

	int rd() { int x = 0;char c = nc();while (c < 48) {c = nc();}while (c > 47) {x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();}return x;}

};

ll qpow(ll base,ll k)

{

	ll tmp=1;

	for(;k;k>>=1,base=base*base%mod) if(k&1) tmp=tmp*base%mod;

	return tmp;

}

int a[N];

int main()

{

	using namespace IO;

	// setIO("input");

	int n=rd(),m=rd(),k=rd(),i,j,ans=1;

	for(i=1;i<=n;++i)

	{

		int x=rd();

		ans=(ll)ans*(k-x)%mod;

	}

	int mdl=1;

	for(i=0;i<=m;++i)

	{

		int x=rd();

		(ans+=(ll)mdl*x%mod)%=mod;

		mdl=(ll)mdl*k%mod;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

nowcoder 181045 / 克洛涅的多项式构造+思维

最新文章

热门文章

巴特西

nowcoder 181045 / 克洛涅的多项式 构造+思维

最新文章

热门文章

nowcoder 181045 / 克洛涅的多项式构造+思维