提交记录 8585


用户 题目 状态 得分 用时 内存 语言 代码长度
Smokey_Days 1002i. 【模板题】多项式乘法 Accepted 100 75.345 ms 6680 KB C++ 1.35 KB
提交时间 评测时间
2019-02-26 21:14:43 2020-08-01 01:22:09
#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353;
const int G = 3, iG = 332748118;
const int MS = 1 << 21;

inline LL qPow(LL b, int e) {
	LL a = 1;
	for (; e; e >>= 1, b = b * b % Mod)
		if (e & 1) a = a * b % Mod;
	return a;
}

int Sz, R[MS]; LL InvSz;

inline void InitFNTT(int N) {
	int Bt = 0;
	while (1 << Bt < N) ++Bt;
	if (Sz == (1 << Bt)) return ;
	Sz = 1 << Bt, InvSz = -(Mod - 1) / Sz;
	for (int i = 0; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}

inline void FNTT(LL *A, int Ty) {
	for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
	for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
		LL gn = qPow(~Ty ? G : iG, (Mod - 1) / j2), g, X, Y;
		for (int i = 0, k; i < Sz; i += j2) {
			for (k = 0, g = 1; k < j; ++k, g = g * gn % Mod) {
				X = A[i + k], Y = g * A[i + j + k] % Mod;
				A[i + k] = (X + Y) % Mod, A[i + j + k] = (X - Y) % Mod;
			}
		}
	}
	if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = A[i] * InvSz % Mod; 
}

int N, M;
LL A[MS], B[MS];

int main(){
	scanf("%d%d", &N, &M);
	for (int i = 0; i <= N; ++i) scanf("%lld", &A[i]);
	for (int i = 0; i <= M; ++i) scanf("%lld", &B[i]);
	InitFNTT(N + M + 1);
	FNTT(A, 1), FNTT(B, 1);
	for (int i = 0; i < Sz; ++i) A[i] = A[i] * B[i] % Mod;
	FNTT(A, -1);
	for (int i = 0; i < N + M + 1; ++i) printf("%lld ", (A[i] + Mod) % Mod);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #110.54 us28 KBAcceptedScore: 0

Subtask #1 Testcase #274.323 ms6 MB + 456 KBAcceptedScore: 100

Subtask #1 Testcase #334.84 ms2 MB + 820 KBAcceptedScore: 0

Subtask #1 Testcase #434.839 ms2 MB + 808 KBAcceptedScore: 0

Subtask #1 Testcase #511.02 us28 KBAcceptedScore: 0

Subtask #1 Testcase #610.2 us28 KBAcceptedScore: 0

Subtask #1 Testcase #79.99 us28 KBAcceptedScore: 0

Subtask #1 Testcase #868.187 ms6 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #968.745 ms6 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #1062.426 ms5 MB + 944 KBAcceptedScore: 0

Subtask #1 Testcase #1174.59 ms6 MB + 536 KBAcceptedScore: 0

Subtask #1 Testcase #1275.345 ms5 MB + 416 KBAcceptedScore: 0

Subtask #1 Testcase #139.47 us28 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2026-04-06 13:40:19 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠