洛谷·拉格朗日差值2

初见安~这个题目好冷门啊……这里是传送门：洛谷P5667 拉格朗日差值2

题解

天知道这个题有多恶心，卡了我一个下午……

乍一看很简单，给你n+1个点值，求一个n次多项式，并求出从m开始的n个点值。

这种情况下就算是用重心差值都不行了，复杂度会达到。怎么办呢——就像那些数学题一样，我们考虑化简公式。

假设当前要求的这个数是m+x。首先我们肯定可以直接套用拉格朗日差值公式：

至此，首先前面那一部分累乘我们明显可以利用m>n这个条件将其转化为阶乘之间的操作：

预处理出阶乘后，这个操作就没有任何问题了。接下来看后面那一坨，设为g（x）。

是不是有点卷积的感觉了？那我们就往卷积的方向去构造。明显我们不能直接提i和n-i出来，那i和n-i+x呢？

所以至此我们就把卷积构造出来啦~~~为什么可以直接取到n+x呢？其实我们把a数组的到都赋值为0就可以了。也就是该怎么算怎么算。

很明显，a数组的取值范围是，b数组为，所以总上限至少为3n。

有一个小细节就是：因为m的范围1e8，不宜预处理信息，所以可以借助关于m的运算有下限这一点进行形如m-n+i的阶乘和逆元的预处理。本狸还是比较懒啦，所以就没有预处理，虽然耗时比较大，但是不会超时。

上代码——

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 600005
using namespace std;
typedef long long ll;
const int mod = 998244353, mx = 6e5;
int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}

int n, m;
ll y[maxn], a[maxn], b[maxn], fac[maxn], inv[maxn];
ll pw(ll a, ll b) {ll res = 1; while(b) {if(b & 1) res =  res * a % mod; a = a * a % mod, b >>= 1;} return res;}

int len = 1, l = 0, r[maxn];
void NTT(ll *c, int flag) {
	for(int i = 1; i <= len; i++) if(i < r[i]) swap(c[i], c[r[i]]);
	for(int mid = 1; mid < len; mid <<= 1) {
		ll gn = pw(3, (mod - 1) / (mid << 1));
		if(flag == -1) gn = pw(gn, mod - 2);
		for(int ls = 0, L = mid << 1; ls < len; ls += L) {
			ll g = 1;
			for(int k = 0; k < mid; k++, g = g * gn % mod) {
				ll tmp = g * c[ls + mid + k] % mod;
				c[ls + mid + k] = (c[ls + k] - tmp + mod) % mod;
				c[ls + k] = (c[ls + k] + tmp) % mod;
			} 
		}
	}
	
	ll rev = pw(len, mod - 2);
	if(flag == -1) for(int i = 0; i <= len; i++) c[i] = c[i] * rev % mod;
}

signed main() {
	n = read(), m = read();
	for(int i = 0; i <= n; i++) y[i] = read();
	
	fac[0] = inv[0] = 1;//预处理阶乘和逆元。虽然阶乘好像并没有用到……
	for(int i = 1; i <= mx; i++) fac[i] = fac[i - 1] * i % mod;
	inv[mx] = pw(fac[mx], mod - 2);
	for(int i = mx - 1; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
	
	while(len <= n + n + n) len <<= 1, l++;
	for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
 	
	for(int i = 0; i <= n + n; i++) b[i] = pw(m - n + i, mod - 2);//b数组每次都算逆元
	for(int i = 0; i <= n; i++) a[i] = (y[i] * ((n - i & 1)? -1 : 1) * inv[i] % mod * inv[n - i] % mod + mod) % mod;
	
	NTT(a, 1), NTT(b, 1);//NTT后直接相乘
	for(int i = 0; i <= len; i++) a[i] = a[i] * b[i] % mod;
	NTT(a, -1);
	ll pre = 1;//pre就是总式前面的那个阶乘，因为m过大所以只好一边求答案一边维护
	for(ll i = m - n; i <= m; i++) pre = pre * i % mod;
	for(ll i = m; i <= n + m; i++) {
		printf("%lld ", (ll)(pre * a[n + i - m] % mod));
		pre = pre * (i + 1) % mod * pw(i - n, mod - 2) % mod;
	}
	return 0;
}

迎评：）
——End——