首页 > 其他分享 >初三多项式的运算练习 题解

初三多项式的运算练习 题解

时间：2024-03-19 16:57:16浏览次数：30  
标签：const int 题解 return 多项式 operator modint 初三 mod

初三多项式的运算练习 题解

美好的下午时光要拿来写题解呜呜呜，一篇一篇地鸽得了。

有些题要用到 GF 的知识，或许我可以找时间讲一下？

贴一份我的 FFT 和 NTT 的板子。

FFT： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, limit, f[1 << 22], g[1 << 22], h[1 << 22];
namespace poly {
	typedef complex<double> cplx;
	const double pi = acos(-1.0);
	void FFT(cplx *f, int limit, double type) {
		static int r[1 << 22];
		for(int i = 1, l = __lg(limit); i < limit; ++i) {
			r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
			if(i < r[i]) swap(f[i], f[r[i]]);
		}
		cplx w, wn, f1, f2;
		for(int mid = 1; mid < limit; mid <<= 1) {
			wn = cos(pi / mid) + type * 1i * sin(pi / mid);
			for(int i = 0; i < limit; i += mid << 1) {
				w = 1.0;
				for(int j = 0; j < mid; ++j, w *= wn) {
					f1 = f[i + j], f2 = w * f[i + mid + j];
					f[i + j] = f1 + f2;
					f[i + mid + j] = f1 - f2;
				}
			}
		}
	}
	void mul(int* F, int n, int *G, int m, int *H) {
		static cplx f[1 << 22], g[1 << 22];
		int l = __lg(n + m) + 1;
		int limit = 1 << l;
		fill(f, f + limit, 0);
		fill(g, g + limit, 0);
		for(int i = 0; i <= n; ++i) f[i].real(F[i]);
		for(int i = 0; i <= m; ++i) g[i].real(G[i]);
		FFT(f, limit, 1.0);
		FFT(g, limit, 1.0);
		for(int i = 0; i < limit; ++i) f[i] *= g[i];
		FFT(f, limit, -1.0);
		for(int i = 0; i <= n + m; ++i) H[i] = int(f[i].real() / limit + 0.5);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i <= n; ++i) cin >> f[i];
	for(int i = 0; i <= m; ++i) cin >> g[i];
	poly::mul(f, n, g, m, h);
	for(int i = 0; i <= n + m; ++i) cout << h[i] << " ";
	return 0;
}

NTT：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace poly {
	constexpr int mod = 998244353, G = 3, gi = 332748118, img = 86583718, inv2 = 499122177, inv2i = 954952494;
	struct modint {
		int x;
		modint(ll v = 0): x((v % mod + mod) % mod) {}
		friend modint ksm(modint x, ll y) {
			modint ret = 1;
			while(y) {if(y & 1) ret *= x; x *= x, y >>= 1;}
			return ret;
		}
		friend modint operator + (const modint& x, const modint& y) {return x.x + y.x >= mod ? x.x + y.x - mod : x.x + y.x;}
		friend modint operator - (const modint& x, const modint& y) {return x.x < y.x ? x.x - y.x + mod : x.x - y.x;}
		friend modint operator * (const modint& x, const modint& y) {return (ll)x.x * y.x % mod;}
		friend modint operator / (const modint& x, const modint& y) {return x * ksm(y, mod - 2);}
		friend modint operator - (const modint& x) {return mod - x.x;}
		modint operator = (const modint& _) {x = _.x; return *this;}
		modint operator += (const modint& _) {*this = *this + _; return *this;}
		modint operator -= (const modint& _) {*this = *this - _; return *this;}
		modint operator *= (const modint& _) {*this = *this * _; return *this;}
		modint operator /= (const modint& _) {*this = *this / _; return *this;}
		bool operator == (const modint& _) const {return x == _.x;}
		bool operator != (const modint& _) const {return x != _.x;}
		friend istream& operator >> (istream& in, modint& _) {static ll tmp; in >> tmp; _.x = tmp % mod; return in;}
		friend ostream& operator << (ostream& out, const modint& _) {return out << _.x;}
	};
	modint ksm(ll x, ll y) {return ksm(modint(x), y);}
	int r[1 << 22];
	modint power[2][23];
	void init(int len) {
		int l = __lg(len) + 1;
		int limit = 1 << l;
		for(int i = 1; i < limit; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
		power[0][l] = ksm(gi, (mod - 1) / limit);
		power[1][l] = ksm(G, (mod - 1) / limit);
		for(int i = l; i >= 1; --i) {
			power[0][i - 1] = power[0][i] * power[0][i];
			power[1][i - 1] = power[1][i] * power[1][i];
		}
	}
	void NTT(modint* f, int n, bool type) {
		for(int i = 1; i < n; ++i) {
			if(i < r[i]) swap(f[i], f[r[i]]);
		}
		modint w, wn, h1, h2;
		for(int mid = 1, lg = 0; mid < n; mid <<= 1, ++lg) {
			wn = power[type][lg + 1];
			for(int i = 0; i < n; i += mid << 1) {
				w = 1;
				for(int j = 0; j < mid; ++j, w *= wn) {
					h1 = f[i + j], h2 = w * f[i + mid + j];
					f[i + j] = h1 + h2, f[i + mid + j] = h1 - h2;
				}
			}
		}
		if(type) return;
		modint inv = ksm(n, mod - 2);
		for(int i = 0; i < n; ++i) f[i] *= inv;
	}
	void mul(modint* F, int n, modint *G, int m, modint *H) {
		static modint f[1 << 22], g[1 << 22];
		int l = __lg(n + m) + 1;
		int limit = 1 << l;
		copy(F, F + limit, f);
		copy(G, G + limit, g);
		init(n + m);
		NTT(f, limit, true);
		NTT(g, limit, true);
		for(int i = 0; i < limit; ++i) H[i] = f[i] * g[i];
		NTT(H, limit, false);
	}
}
using poly::modint;
int n, m;
modint f[1 << 22], g[1 << 22], h[1 << 22];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i <= n; ++i) cin >> f[i];
	for(int i = 0; i <= m; ++i) cin >> g[i];
	poly::mul(f, n, g, m, h);
	for(int i = 0; i <= n + m; ++i) cout << h[i] << " ";
	return 0;
}

力老师

先把 \(q_{j}\) 从 \(F_{j}\) 中消掉。

再把 \(F_{j}\) 分成两部分算，一个 \(\sum\limits_{i = 1}^{j - 1}\dfrac{q_{i}}{(i - j)^{2}}\) 一个 \(-\sum\limits_{i = j + 1}^{n}\dfrac{q_{i}}{(i - j)^{2}}\)。

令多项式 \(Q(x) = \sum\limits_{i = 1}^{n}q_{i}x^{i}\)，也就是 \([x^{i}]Q(x) = q_{i}\)，特别的，\([x^{0}]Q(x) = 0\)。

令多项式 \(G(x) = \sum\limits_{i = 1}^{n}\dfrac{x^{i}}{i^{2}}\)，也就是 \([x^{i}]G(x) = \dfrac{1}{i^{2}}\)，特别的，\([x^{0}]G(x) = 0\)。

然后把上面的式子替换成多项式的系数的运算，有：

\[\begin{aligned} \sum\limits_{i = 1}^{j - 1}\dfrac{q_{i}}{(i - j)^{2}} &= \sum\limits_{i = 1}^{j - 1}[x^{i}]Q(x) \times [x^{j - i}]G(x)\\ &= \sum\limits_{i = 0}^{j}[x^{i}]Q(x) \times [x^{j - i}]G(x)\\ \sum\limits_{i = j + 1}^{n}\dfrac{q_{i}}{(i - j)^{2}} &= \sum\limits_{i = j + 1}^{n}[x^{i}]Q(x) \times [x^{i - j}]G(x)\\ &= \sum\limits_{i = j}^{n}[x^{i}]Q(x) \times [x^{i - j}]G(x) \end{aligned} \]

可以发现上面的部分就是一个卷积的形式，下面的部分是一个「差卷积」，把其中一个多项式的次数反转一下即可（即令 \([x^{i}]H(x) = [x^{n - i + 1}]G(x)\)）。

代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int lim = 1 << 18;
namespace poly {
	typedef complex<double> cplx;
	const double pi = acos(-1.0);
	void FFT(cplx *f, int limit, double type) {
		static int r[lim];
		for(int i = 1, l = __lg(limit); i < limit; ++i) {
			r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
			if(i < r[i]) swap(f[i], f[r[i]]);
		}
		cplx w, wn, f1, f2;
		for(int mid = 1; mid < limit; mid <<= 1) {
			wn = cos(pi / mid) + type * 1i * sin(pi / mid);
			for(int i = 0; i < limit; i += mid << 1) {
				w = 1.0;
				for(int j = 0; j < mid; ++j, w *= wn) {
					f1 = f[i + j], f2 = w * f[i + mid + j];
					f[i + j] = f1 + f2;
					f[i + mid + j] = f1 - f2;
				}
			}
		}
	}
	void mul(double* F, int n, double *G, int m, double *H) {
		static cplx f[lim], g[lim];
		int l = __lg(n + m) + 1;
		int limit = 1 << l;
		fill(f, f + limit, 0);
		fill(g, g + limit, 0);
		for(int i = 0; i <= n; ++i) f[i].real(F[i]);
		for(int i = 0; i <= m; ++i) g[i].real(G[i]);
		FFT(f, limit, 1.0);
		FFT(g, limit, 1.0);
		for(int i = 0; i < limit; ++i) f[i] *= g[i];
		FFT(f, limit, -1.0);
		for(int i = 0; i <= n + m; ++i) H[i] = f[i].real() / limit;
	}
}
int n;
double q[lim], i2[lim], res1[lim], res2[lim];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> q[i];
		i2[i] = 1.0 / i / i;
	}
	poly::mul(q, n, i2, n, res1);
	reverse(q + 1, q + 1 + n);
	poly::mul(q, n, i2, n, res2);
	for(int i = 1; i <= n; ++i) {
		cout << fixed << setprecision(3) << res1[i] - res2[n - i + 1] << '\n';
	}
	return 0;
}

咕咕咕捏。

标签：const,int,题解,return,多项式,operator,modint,初三,mod
From： https://www.cnblogs.com/A-box-of-yogurt/p/18083310

相关文章

  • 洛谷 P2934 [USACO09JAN] Safe Travel G 题解
    前话貌似别人都是使用并查集维护的方法，然而由于排序、最短路等算法瓶颈，以下令\(n\)和\(m\)同阶，总的时间复杂度依然是\(\Theta(n\logn)\)的，那么并查集是否有点大材小用了。事实上，在建完最短路径树后，我给出了两种带\(\log\)的数据结构完成此题。题目分析翻译里已经把问......
  • 腾讯春招内参：2024最全Spring Boot面试题解析，技术精英必备！
    随着2024年春季招聘季的来临，腾讯再次开启了对富有才华和创新精神的技术人才的寻找之旅。作为一家全球领先的互联网科技公司，腾讯在寻找那些不仅拥有扎实的技术基础，而且能够适应快速发展和变化的行业环境的候选人。在众多技术栈中，SpringBoot作为简化Spring应用开发的工具，因其......
  • AtCoder Beginner Contest 345 A-F 题解
    A-LeftrightarrowQuestion给你一个由<、=和>组成的字符串\(S\)。请判断\(S\)是否是双向箭头字符串。字符串\(S\)是双向箭头字符串，当且仅当存在一个正整数\(k\)，使得\(S\)是一个<、\(k\)个=和一个>的连接，且顺序如此，长度为\((k+2)\)。Solution按照题意......
  • 分月饼【华为OD机试JAVA&Python&C++&JS题解】
    一.题目-分月饼中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2<=3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1)–Max(n)<=3,问有多少......
  • ARC174C 题解
    blog。官解似乎很难想到，这里是容易想到的方法。显然是DP。介于轮数可能趋近于无穷，所以类似P4550做即可。设\(f_i,g_i\)表示已经抽了\(i\)个数，当前是Alice或Bob抽的，期望罚款。倒推处理，\(f_n=g_n=0\)。下文中\(p=\dfracin\)表示抽到已经有的概率。\[\large\begin......
  • [极客大挑战 2019]web部分题解（sql部分已完结，其他部分正在更新）
    SQL部分：[极客大挑战2019]BabySQL打开环境后有登录界面◕‿◕一眼注入，后先试试万能密码：username：admin'or'1'='1password：1 GG，出大问题，我就会这一招啊O.o？？完结撒花（不是꒰ঌ(⌯''⌯)໒꒱开玩笑的，着看着像是过滤了or后来尝试了一下oorr双写发现也不行，那咱继续注入哈：尝试......
  • 题解：CF1941G Rudolf and Subway
    原题链接简化题意一个无向连通图中将边分成了不同颜色（保证同种颜色联通），问从\(b\)到\(e\)最短需要经过几种颜色思路考虑因为同种颜色联通，可直接在读入的时候开两个vector分别存每个点属于的颜色及每种颜色有哪些点，又因为颜色数字可能跨度比较大，最好另开一个存颜色的种......
  • P9077 [PA2018] Poddrzewo 题解
    思考感觉题目有点迷惑的意思，要最小化操作\(1\)使用的次数，也就是要节约修改操作，让我们认为操作\(1\)是最有用的，其实只要稍微动动脑子想一想，删除操作才是最有用的，而交换操作根本没用。当将序列删除到只剩两个点时，就把两个点连上，度都为\(1\)。所以如果序列中\(1\)的数量超......
  • 亲子游戏【华为OD机试JAVA&Python&C++&JS题解】
    题目描述宝宝和妈妈参加亲子游戏，在一个二维矩阵（NN）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下......
  • SGU171 Sarov zones 题解
    题意：有\(K\)个城市，第\(i\)城市至多有\(N[i]\)个人，每个城市有一个属性\(Q[i]\)。对于\(N=\sumN[i]\)个人，每个人有一个属性\(P[i]\)和价值\(W[i]\)，把第\(i\)个人放进第\(j\)个城市中，当且仅当\(P[i]>Q[j]\)时，可以获得\(W[i]\)的价值，否则不获得价值。求出满......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99