UOJ#34. 多项式乘法(NTT)
2018-06-17 20:42:33来源:未知 阅读 ()
这是一道模板题。
给你两个多项式,请输出乘起来后的多项式。
输入格式
第一行两个整数 nn 和 mm,分别表示两个多项式的次数。
第二行 n+1n+1 个整数,表示第一个多项式的 00 到 nn 次项系数。
第三行 m+1m+1 个整数,表示第二个多项式的 00 到 mm 次项系数。
输出格式
一行 n+m+1n+m+1 个整数,表示乘起来后的多项式的 00 到 n+mn+m 次项系数。
样例一
input
1 2 1 2 1 2 1
output
1 4 5 2
explanation
(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3。
限制与约定
0≤n,m≤1050≤n,m≤105,保证输入中的系数大于等于 00 且小于等于 99。
时间限制:1s1s
空间限制:256MB
震惊!
TLE一上午的原因竟然是素数和原根的定义没有加const!
NTT的板子题
把单位元换成原根就好
#include<cstdio> #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++) #define swap(x,y) x ^= y, y ^= x, x ^= y #define LL long long const int MAXN = 3 * 1e6 + 10, P = 998244353, G = 3, Gi = 332748118; char buf[1<<21], *p1 = buf, *p2 = buf; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, limit = 1, L, r[MAXN]; LL a[MAXN], b[MAXN]; inline LL fastpow(LL a, LL k) { LL base = 1; while(k) { if(k & 1) base = (base * a ) % P; a = (a * a) % P; k >>= 1; } return base % P; } inline void NTT(LL *A, int type) { for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]); for(int mid = 1; mid < limit; mid <<= 1) { LL Wn = fastpow( type == 1 ? G : Gi , (P - 1) / (mid << 1)); for(int j = 0; j < limit; j += (mid << 1)) { LL w = 1; for(int k = 0; k < mid; k++, w = (w * Wn) % P) { int x = A[j + k], y = w * A[j + k + mid] % P; A[j + k] = (x + y) % P, A[j + k + mid] = (x - y + P) % P; } } } } int main() { N = read(); M = read(); for(int i = 0; i <= N; i++) a[i] = (read() + P) % P; for(int i = 0; i <= M; i++) b[i] = (read() + P) % P; while(limit <= N + M) limit <<= 1, L++; for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1)); NTT(a, 1);NTT(b, 1); for(int i = 0; i < limit; i++) a[i] = (a[i] * b[i]) % P; NTT(a, -1); LL inv = fastpow(limit, P - 2); for(int i = 0; i <= N + M; i++) printf("%d ", (a[i] * inv) % P); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:关系运算符
- 多项式方程的输出 2019-10-16
- 矩阵乘法(五):置换 2019-09-08
- 矩阵乘法(七):其它一些典型应用 2019-09-08
- 矩阵乘法(六):几何变换 2019-09-08
- 矩阵乘法(四):分析问题,确定递推式,采用矩阵快速幂求解 2019-09-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash