首页 > 其他分享 >多项式学习笔记（二）（2024.7.23）

多项式学习笔记（二）（2024.7.23）

时间：2024-09-20 16:52:27浏览次数：11  
标签：2024.7 int 多项式 23 rev ++ lim lng MOD

牛顿迭代

快速多项式计算

加法

\(H(x) = F(x) + G(x)\)，求\(H(x)\)

解：都已经\(O(n)\)了，还怎么优化！！！

乘法

\(H(x) \equiv F(x)G(x) (\text{mod }x^n)\)，求\(H(x)\)

解：参考多项式学习笔记（一）（2024.7.6）

完整代码：P3803 【模板】多项式乘法（FFT）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6 + 9, MOD = 998244353;
int rev[N];
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int f[N << 1], g[N << 1], n, m;
signed main(){
	scanf("%lld%lld", &n, &m);
	for(int i = 0; i <= n; i++)
		scanf("%lld", &f[i]);
	for(int i = 0; i <= m; i++)
		scanf("%lld", &g[i]);
	int lim = 1;
	while(lim <= n + m)
		lim <<= 1;
	NTT(f, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i <= lim; i++)
		f[i] = f[i] * g[i] % MOD;
	NTT(f, lim, -1); 
	for(int i = 0; i <= n + m; i++)
		printf("%lld ", f[i]);
	return 0;
}

求逆

\(F(x)G(x) \equiv 1 (\text{mod }x^n)\)

求\(G(x)\)

解：

完整代码：P4238 【模板】多项式乘法逆

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6 + 9, MOD = 998244353;
int rev[N];
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int tmp[N << 1];
void solve(int *f, int *g, int n){
	if(!n){
		g[0] = qpow(f[0], MOD - 2);
		return;
	}
	solve(f, g, n >> 1);
	int lim = 1;
	while(lim <= n * 2 + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++)
		tmp[i] = f[i];
	NTT(tmp, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = (2 - g[i] * tmp[i] % MOD + MOD) % MOD * g[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f[N << 1], g[N << 1], n;
signed main(){
	scanf("%lld", &n);
	n--;
	for(int i = 0; i <= n; i++)
		scanf("%lld", &f[i]);
	solve(f, g, n);
	for(int i = 0; i <= n; i++)
		printf("%lld ", g[i]);
	return 0;
}

除法/取模

\(F(x)\equiv Q(x)G(x)+R(x)(\text{mod }{x^n})\)

求\(Q(x),R(x)\)

解：

完整代码：P4512 【模板】多项式除法

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6 + 9, MOD = 998244353;
int rev[N];
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int tmp[N << 1];
void inv(int *f, int *g, int n){
	if(!n){
		g[0] = qpow(f[0], MOD - 2);
		return;
	}
	inv(f, g, n >> 1);
	int lim = 1;
	while(lim <= n * 2 + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++)
		tmp[i] = f[i];
	NTT(tmp, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = (2 - g[i] * tmp[i] % MOD + MOD) % MOD * g[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
void div(int *f, int *g, int len1, int len2){
	int lim = 1;
	while(lim <= len1 + len2)
		lim <<= 1;
	NTT(f, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i <= lim; i++)
		f[i] = f[i] * g[i] % MOD;
	NTT(f, lim, -1);
}
int f[N << 1], g[N << 1], r[N << 1], q[N << 1], rf[N << 1], rg[N << 1], rr[N << 1], n, m;
signed main(){
	scanf("%lld%lld", &n, &m);
	for(int i = 0; i <= n; i++){
		scanf("%lld", &f[i]);
		rf[n - i] = f[i];
	}
	for(int i = 0; i <= m; i++){
		scanf("%lld", &g[i]);
		rg[m - i] = g[i];
	}
	for(int i = n - m + 1; i <= m; i++)
		rg[i] = 0;
	inv(rg, rr, n - m);
	div(rf, rr, n, n - m);
	for(int i = 0; i <= n - m; i++)
		printf("%lld ", q[i] = rf[n - m - i]);
	printf("\n");
	div(g, q, m, n - m);
	for(int i = 0; i < m; i++)
		printf("%lld ", r[i] = (f[i] - g[i] + MOD) % MOD);
	return 0;
}

求导/积分

\(G(x) = F'(x)\)

\(H(x) = \displaystyle\int F(x)dx\)

求\(G(x),H(x)\)

解：都已经\(O(n)\)了，还怎么优化！！！

完整代码：U455122 【模板】多项式求导/积分

开根

\(G^2(x) \equiv F(x)(\text{mod }{x^n})\)

求\(G(x)\)

解：

完整代码：P5205 【模板】多项式开根

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 9, MOD = 998244353;
int rev[N], in[N];
void init(){
	in[1] = 1;
	for(int i = 2; i <= N; i++)
		in[i] = (MOD - MOD / i) * in[MOD % i] % MOD;
}
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int tmp[N << 1];
void inv(int *f, int *g, int n){
	if(!n){
		g[0] = qpow(f[0], MOD - 2);
		return;
	}
	inv(f, g, n >> 1);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++)
		tmp[i] = f[i];
	for(int i = n + 1; i < lim; i++)
		tmp[i] = 0;
	NTT(tmp, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = (2 - g[i] * tmp[i] % MOD + MOD) % MOD * g[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f2[N << 1];
void ln(int *f, int *g, int n){
	for(int i = 0; i < n * 4 + 3; i++)
		g[i] = 0;
	inv(f, g, n);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i < n; i++)
		f2[i] = f[i + 1] * (i + 1) % MOD;
	for(int i = n; i < lim; i++)
		f2[i] = 0;
	NTT(f2, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * f2[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n; i > 0; i--)
		g[i] = g[i - 1] * in[i] % MOD;
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
	g[0] = 0;
}
int lng[N << 1];
void exp(int *f, int *g, int n){
	if(!n){
		g[0] = 1;
		return;
	}
	exp(f, g, n >> 1);
	ln(g, lng, n);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++){
		if(f[i] >= lng[i])
			lng[i] = f[i] - lng[i];
		else
			lng[i] = f[i] - lng[i] + MOD;
	}
	for(int i = n + 1; i < lim; i++)
		lng[i] = g[i] = 0;
	lng[0]++;
	NTT(lng, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * lng[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f[N << 1], g[N << 1], res[N << 1], n, k;
char s[1009];
signed main(){
	init();
	scanf("%lld", &n);
	n--;
	for(int i = 0; i <= n; i++)
		scanf("%lld", &f[i]);
	ln(f, g, n);
	int inv = qpow(2, MOD - 2);
	for(int i = 0; i <= n; i++)
		g[i] = g[i] * inv % MOD;
	exp(g, res, n);
	for(int i = 0; i <= n; i++)
		printf("%lld ", res[i]);
	return 0;
}

P5277 【模板】多项式开根（加强版）

对数函数

\(G(x) \equiv \text{ln }F(x)(\text{mod } x^n)\)，保证\(f_0 = 1\)

求\(G(x)\)

解：

完整代码：P4725 【模板】多项式对数函数（多项式 ln）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6 + 9, MOD = 998244353;
int rev[N], in[N];
void init(){
	in[1] = 1;
	for(int i = 2; i <= N; i++)
		in[i] = (MOD - MOD / i) * in[MOD % i] % MOD;
}
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int tmp[N << 1];
void inv(int *f, int *g, int n){
	if(!n){
		g[0] = qpow(f[0], MOD - 2);
		return;
	}
	inv(f, g, n >> 1);
	int lim = 1;
	while(lim <= n * 2 + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++)
		tmp[i] = f[i];
	NTT(tmp, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = (2 - g[i] * tmp[i] % MOD + MOD) % MOD * g[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f2[N << 1];
void ln(int *f, int *g, int n){
	inv(f, g, n);
	int lim = 1;
	while(lim <= n * 2 + 1)
		lim <<= 1;
	for(int i = 0; i < n; i++)
		f2[i] = f[i + 1] * (i + 1) % MOD;
	for(int i = n; i < lim; i++)
		f2[i] = 0;
	NTT(f2, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * f2[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n; i > 0; i--)
		g[i] = g[i - 1] * in[i] % MOD;
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
	g[0] = 0;
}
int f[N << 1], g[N << 1], n;
signed main(){
	init();
	scanf("%lld", &n);
	n--;
	for(int i = 0; i <= n; i++)
		scanf("%lld", &f[i]);
	ln(f, g, n);
	for(int i = 0; i <= n; i++)
		printf("%lld ", g[i]);
	return 0;
}

指数函数

\(G(x) \equiv e^{F(x)}(\text{mod } x^n)\)，保证\(f_0 = 0\)

求：\(G(x)\)

解：

完整代码：P4726 【模板】多项式指数函数（多项式 exp）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6 + 9, MOD = 998244353;
int rev[N], in[N];
void init(){
	in[1] = 1;
	for(int i = 2; i <= N; i++)
		in[i] = (MOD - MOD / i) * in[MOD % i] % MOD;
}
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int tmp[N << 1];
void inv(int *f, int *g, int n){
	if(!n){
		g[0] = qpow(f[0], MOD - 2);
		return;
	}
	inv(f, g, n >> 1);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++)
		tmp[i] = f[i];
	for(int i = n + 1; i < lim; i++)
		tmp[i] = 0;
	NTT(tmp, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = (2 - g[i] * tmp[i] % MOD + MOD) % MOD * g[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f2[N << 1];
void ln(int *f, int *g, int n){
	for(int i = 0; i < n * 4 + 3; i++)
		g[i] = 0;
	inv(f, g, n);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i < n; i++)
		f2[i] = f[i + 1] * (i + 1) % MOD;
	for(int i = n; i < lim; i++)
		f2[i] = 0;
	NTT(f2, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * f2[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n; i > 0; i--)
		g[i] = g[i - 1] * in[i] % MOD;
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
	g[0] = 0;
}
int lng[N << 1];
void exp(int *f, int *g, int n){
	if(!n){
		g[0] = 1;
		return;
	}
	exp(f, g, n >> 1);
	ln(g, lng, n);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++){
		if(f[i] >= lng[i])
			lng[i] = f[i] - lng[i];
		else
			lng[i] = f[i] - lng[i] + MOD;
	}
	for(int i = n + 1; i < lim; i++)
		lng[i] = g[i] = 0;
	lng[0]++;
	NTT(lng, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * lng[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f[N << 1], g[N << 1], n;
signed main(){
	init();
	scanf("%lld", &n);
	n--;
	for(int i = 0; i <= n; i++)
		scanf("%lld", &f[i]);
	exp(f, g, n);
	for(int i = 0; i <= n; i++)
		printf("%lld ", g[i]);
	return 0;
}

幂函数

\(G(x) \equiv F^k(x)(\text{mod } x ^ n)\)

求\(G(x)\)

解：

完整代码：P5245 【模板】多项式快速幂

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e6 + 9, MOD = 998244353;
int rev[N], in[N];
void init(){
	in[1] = 1;
	for(int i = 2; i <= N; i++)
		in[i] = (MOD - MOD / i) * in[MOD % i] % MOD;
}
int qpow(int x, int y){
	int res = 1;
	while(y){
		if(y & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}
void NTT(int *f, int n, int opt){
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1;
		if(i % 2 == 1)
			rev[i] |= n >> 1;
	}
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(f[i], f[rev[i]]);
	for(int h = 2; h <= n; h <<= 1){
		int mi = h >> 1;
		int gn = qpow(3, (MOD - 1) / h);
		for(int j = 0; j < n; j += h){
			int g = 1;
			for(int k = 0; k < mi; k++){
				int tmp = f[j + k + mi] * g % MOD;
				f[j + k + mi] = (f[j + k] - tmp + MOD) % MOD;
				f[j + k] = (f[j + k] + tmp) % MOD;
				g = g * gn % MOD;
			}
		}
	}
	if(opt == -1){
		reverse(f + 1, f + n);
	    int inv = qpow(n, MOD - 2);
	    for(int i = 0; i < n; i++)
			f[i] = f[i] * inv % MOD;
	}
}
int tmp[N << 1];
void inv(int *f, int *g, int n){
	if(!n){
		g[0] = qpow(f[0], MOD - 2);
		return;
	}
	inv(f, g, n >> 1);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++)
		tmp[i] = f[i];
	for(int i = n + 1; i < lim; i++)
		tmp[i] = 0;
	NTT(tmp, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = (2 - g[i] * tmp[i] % MOD + MOD) % MOD * g[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f2[N << 1];
void ln(int *f, int *g, int n){
	for(int i = 0; i < n * 4 + 3; i++)
		g[i] = 0;
	inv(f, g, n);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i < n; i++)
		f2[i] = f[i + 1] * (i + 1) % MOD;
	for(int i = n; i < lim; i++)
		f2[i] = 0;
	NTT(f2, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * f2[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n; i > 0; i--)
		g[i] = g[i - 1] * in[i] % MOD;
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
	g[0] = 0;
}
int lng[N << 1];
void exp(int *f, int *g, int n){
	if(!n){
		g[0] = 1;
		return;
	}
	exp(f, g, n >> 1);
	ln(g, lng, n);
	int lim = 1;
	while(lim < 2 * n + 1)
		lim <<= 1;
	for(int i = 0; i <= n; i++){
		if(f[i] >= lng[i])
			lng[i] = f[i] - lng[i];
		else
			lng[i] = f[i] - lng[i] + MOD;
	}
	for(int i = n + 1; i < lim; i++)
		lng[i] = g[i] = 0;
	lng[0]++;
	NTT(lng, lim, 1);
	NTT(g, lim, 1);
	for(int i = 0; i < lim; i++)
		g[i] = g[i] * lng[i] % MOD;
	NTT(g, lim, -1);
	for(int i = n + 1; i < lim; i++)
		g[i] = 0;
}
int f[N << 1], g[N << 1], res[N << 1], n, k;
char s[10000009];
signed main(){
	init();
	scanf("%lld%s", &n, s + 1);
	n--;
	int len = strlen(s + 1);
	for(int i = 1; i <= len; i++)
		k = ((k << 3) + (k << 1) + (s[i] - 48)) % MOD;
	for(int i = 0; i <= n; i++)
		scanf("%lld", &f[i]);
	ln(f, g, n);
	for(int i = 0; i <= n; i++)
		g[i] = g[i] * k % MOD;
	exp(g, res, n);
	for(int i = 0; i <= n; i++)
		printf("%lld ", res[i]);
	return 0;
}

P5273 【模板】多项式幂函数（加强版）

三角函数

\(G(x) = \text{sin }F(x)\)

\(H(x) = \text{cos }F(x)\)

求\(G(x),H(x)\)

解：

完整代码：P5264 多项式三角函数

第二类斯特林数

生成函数

标签：2024.7,int,多项式,23,rev,++,lim,lng,MOD
From： https://www.cnblogs.com/JPGOJCZX/p/18422809

相关文章

  • 线性代数学习笔记（一）（2024.7.24）
    向量定义从偏计算机的角度分析，这是排成一列的数。从偏物理的角度分析，这是一条有方向有长度的线段。可以通过数形结合的方式来理解向量。虽然向量的起点不固定，但画平面直角坐标系中的向量，我们一般将向量的起点放在\((0,0)\)，用向量的终点表示这个向量，如图：这个向量可以表示......
  • 数论学习笔记（一）（2024.7.25）
    一、最大公约数定义不全为\(0\)的整数\(a,b\)的最大公约数是指能够同时整除\(a\)和\(b\)的最大整数。欧几里得算法(gcd)gcd是用来求解两个整数的最大公约数定理1.2.1对于整数\(a,b,m,n\)，若\(c\mida，c\midb\)，则\(c\mid(ma+nb)\)证：\(\becausec\mida......
  • GEE教程：1950-2023年ECMWF数据中积雪的长时序统计分析
    目录简介数据函数millis()Arguments:Returns: Long代码结果简介1950-2023年ECMWF数据中积雪的长时序统计分析数据ECMWF/ERA5_LAND/DAILY_AGGR是由欧洲中期天气预报中心（ECMWF）提供的数据集。它是一个格网数据集，包含从ERA5-Land再分析数据集中得出的陆地区域每日聚......
  • 线段树进阶应用学习笔记（一）（2024.7.19）（2024.8.22）
    线段树优化建图算法流程复杂度分析例题一#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=5e5,M=5e6+9;structEdge{ intv,w,nex;}e[M];inthead[M],ecnt;voidAddEdge(intu,intv,intw){ e[++ecnt]=Edge{v,w,hea......
  • 平衡树学习笔记（一）（2024.7.20）
    二叉搜索树众所周知，一个区间可以有许多信息(最大值、\(k\)大值、区间和、区间平方和、区间立方和、区间异或和、区间\(\gcd\)、不同数字个数、颜色段数……)，也有许多修改方式(插入、删除、区间加、区间乘、区间改、区间翻转……)，我们发现其中一些用线段树不是很好维护，这时我们......
  • COSC2391 Further Programming
    COSC2391 FurtherProgramming/COSC1295AdvancedProgrammingAssignment2- Semester 2 20241.IntroductionThisassignmentisdesignedto:•   Evaluateyourabilitytodevelop GUI applications usingJavaFX.•   Evaluateyourskillsin stori......
  • D23 kubernetes 工作负载资源对象-DaemonSet{简介}
    1、DaemonSet简介DaemonSet资源用于在集群中的每个节点上运行一个pod副本，具有以下特点-在每个节点上运行一个pod-当向集群中加入一个新节点或者从集群中移除一个节点时，DaemonSet会自动在新节点上启动一个pod或在移除的节点上删除pod-可以使用节点选择器或亲和性来定义pod......
  • 10月23日，2024 OceanBase 年度发布会在北京等您
    海量数据管理，源于一笔笔记录， 不止于记录， 不仅要保障每一笔记录，更要实现每一份数据的价值。OceanBase正通过一体化架构和一体化引擎，不断创新实现 一体化的TP、AP和多模融合的多工作负载， 从线下到云端，全面加速基于跨分布式数据的创新。2024年10月23日，OceanBase将在北......
  • springboot社区医院管理信息系统-计算机毕业设计源码23303
    摘 要本文旨在探讨基于SpringBoot框架的社区医院管理信息系统的设计与实现。随着信息技术的快速发展，医院管理信息化已成为提升医疗服务水平、优化医疗资源配置的重要手段。社区医院作为基层医疗服务的重要组成部分，其信息化建设的推进对于提高基层医疗服务质量和效率具有......
  • 世界前沿科技大会暨23届“一带一路”技术转移与国际合作创新论坛签约合作项目超100亿
    9月14日，由中国国际科技促进会、中国-阿拉伯国家青年创业园管委会、阿拉伯国家-中国经贸合作创新中心联合阿拉伯大学协会、阿联酋2031 愿景全球战略伙伴中心、中国-阿拉伯国家联合商会宁夏联络办公室、中国-柬埔寨技术转移中心、摩洛哥AI2SD全球峰会组委会、国际标识代码产业联......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99