G74【模板】拉格朗日插值法

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=3010;
const ll mod=998244353;
int n,m;
ll x[N],y[N],a[N],sum[N];
ll ksm(ll a,ll b)
{
	ll res=1ll;
	for(;b;b>>=1ll,a=a*a%mod)if(b&1ll) res=res*a%mod;
	return res;
}
int main()
{
	scanf("%d",&m),n=0;
	for(int i=1,op;i<=m;i++){
		scanf("%d",&op);
		if(op==1)
		{
			n++,scanf("%lld%lld",&x[n],&y[n]),sum[n]=1;
			for(int j=1;j<=n-1;j++)
				sum[n]=sum[n]*(x[n]-x[j]+mod)%mod,
				sum[j]=sum[j]*(x[j]-x[n]+mod)%mod;
		}
		else
		{
			ll k;scanf("%lld",&k);
			bool flag=0;ll t=1;
			for(int j=1;j<=n;j++)
			{
				if(k==x[j])
				{
					printf("%lld\n",y[j]);
					flag=1;
					break;
				}
				t=t*(k-x[j]+mod)%mod;
			}
			if(flag) continue;
			ll ans=0;
			for(int j=1;j<=n;j++)
				ans+=y[j]*ksm(sum[j],mod-2)%mod*t%mod*ksm(k-x[j]+mod,mod-2)%mod,
				ans-=(ans>=mod)?mod:0;

			printf("%lld\n",ans);
		}
	}
	return 0;
}

G74【模板】拉格朗日插值法

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=3010; const ll mod=998244353; int n,m; ll x[N],y[N],a[N],sum[N]; ll ksm(ll a,ll b) { ll res=1ll; for(;b;b>>=1ll,a=aa%mod)if(b&1ll) res=resa%mod; return res; } int main() { scanf("%d",&m),n=0; for(int i=1,op;i<=m;i++){ scanf("%d",&op); if(op1) { n++,scanf("%lld%lld",&x[n],&y[n]),sum[n]=1; for(int j=1;j<=n-1;j++) sum[n]=sum[n](x[n]-x[j]+mod)%mod, sum[j]=sum[j](x[j]-x[n]+mod)%mod; } else { ll k;scanf("%lld",&k); bool flag=0;ll t=1; for(int j=1;j<=n;j++) { if(kx[j]) { printf("%lld\n",y[j]); flag=1; break; } t=t*(k-x[j]+mod)%mod; } if(flag) continue; ll ans=0; for(int j=1;j<=n;j++) ans+=y[j]ksm(sum[j],mod-2)%modt%mod*ksm(k-x[j]+mod,mod-2)%mod, ans-=(ans>=mod)?mod:0;

		printf("%lld\n",ans);
	}
}
return 0;

}</pre>