提交记录 13228

用户 题目 状态 得分 用时 内存 语言 代码长度
Siyuan 1002i. 【模板题】多项式乘法 Accepted 100 67.618 ms 8252 KB C++11 8.31 KB
提交时间 评测时间
2020-08-01 08:19:49 2020-08-01 08:19:54 
#include <bits/stdc++.h>

typedef unsigned int uint;
typedef unsigned long long uint64;

const uint MOD = 998244353, G = 3;
const uint I2 = 499122177, I3 = 332748118;

struct Z {
	uint v;
	Z() {}
	Z(const uint &v) : v(v) {}
	inline bool operator < (const Z &x) const {
		return v < x.v;
	}
};

inline uint norm(const uint &x) {
	return x < MOD ? x : x - MOD;
}
inline Z operator + (const Z &a, const Z &b) {
	return norm(a.v + b.v);
}
inline Z operator - (const Z &a, const Z &b) {
	return norm(a.v + MOD - b.v);
}
inline Z operator - (const Z &a) {
	return a.v > 0 ? MOD - a.v : 0;
}
inline Z operator * (const Z &a, const Z &b) {
	return static_cast<uint64>(a.v) * b.v % MOD;
}
inline Z &operator += (Z &a, const Z &b) {
	return a = a + b;
}
inline Z &operator -= (Z &a, const Z &b) {
	return a = a - b;
}
inline Z &operator *= (Z &a, const Z &b) {
	return a = a * b;
}
inline Z power(Z x, int k) {
	Z ans = 1;
	for (; k > 0; k >>= 1, x *= x) {
		if (k & 1) {
			ans *= x;
		}
	}
	return ans;
}
inline Z inv(const Z &x) {
	return power(x, MOD - 2);
}
inline int ceilLog(const int &n) {
	return std::__lg((n << 1) - 1);
}
inline int bsgs(Z a, Z b) {
	if (b.v == 1) {
		return 0;
	}
	int m = ceil(sqrt(MOD));
	std::unordered_map<uint, int> map;
	Z w(1);
	for (int i = 0; i < m; i++, b *= a, w *= a) {
		map[b.v] = i;
	}
	a = w;
	for (int i = 1; i <= m; a *= w) {
		if (map.count(a.v)) {
			return i * m - map[a.v];
		}
	}
	return -1;
}
inline Z degree(Z x, int k) {
	if (x.v == 0) {
		return 0;
	}
	int r = bsgs(G, x);
	assert(r >= 0 && r % k == 0);
	x = power(G, r / k);
	return std::min(x, -x);
}




typedef std::vector<Z> Poly;

void reset(Poly &A, int n) {
    A.clear();
    A.resize(n, 0);
}
Poly slice(const Poly &A, int l, int r) {
    Poly B(r - l + 1, 0);
	std::copy_n(A.data() + l, r - l + 1, B.data());
	return B;
}
Poly slice(const Poly &A, int n) {
    Poly B(n, 0);
	std::copy_n(A.data(), n, B.data());
	return B;
}
inline Poly operator + (const Poly &A, const Poly &B) {
	Poly C(A);
	C.resize(std::max(A.size(), B.size()), 0);
	for (int i = 0; i < (int)B.size(); i++) {
		C[i] += B[i];
	}
	return C;
}
inline Poly operator + (const Poly &A, const Z &w) {
	return A + Poly({w});
}
inline Poly operator + (const Z &w, const Poly &A) {
	return A + Poly({w});
}
inline Poly operator - (const Poly &A, const Poly &B) {
	Poly C(A);
	C.resize(std::max(A.size(), B.size()), 0);
	for (int i = 0; i < (int)B.size(); i++) {
		C[i] -= B[i];
	}
	return C;
}
inline Poly operator - (const Poly &A, const Z &w) {
	return A - Poly({w});
}
inline Poly operator - (const Z &w, const Poly &A) {
	return Poly({w}) - A;
}
inline Poly operator - (const Poly &A) {
	Poly B(A);
	for (auto &x : B) {
		x = -x;
	}
	return B;
}
inline Poly operator * (const Z &k, const Poly &A) {
	Poly B(A);
	for (auto &x : B) {
		x *= k;
	}
	return B;
}
inline Poly operator * (const Poly &A, const Z &k) {
	Poly B(A);
	for (auto &x : B) {
		x *= k;
	}
	return B;
}



namespace NTT {
	std::vector<Z> w[21];

	inline void init(int k) {
		for (int i = 1; i <= k; i++) {
			w[i].resize(1 << i, 0);
			Z root = power(G, (MOD - 1) >> i);
			w[i][0] = 1;
			for (int j = 1; j < (1 << i); j++) {
				w[i][j] = w[i][j - 1] * root;
			}
		}
	}
	inline void ntt(Poly &P, int k, bool opt) {
		Z *A = P.data();
		int n = 1 << k;
		std::vector<int> rev(n, 0);
		for (int i = 0; i < n; i++) {
			rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
			if (i < rev[i]) {
				std::swap(A[i], A[rev[i]]);
			}
		}
		for (int l = 1, t = 1; l < n; l <<= 1, t++) {
			for (int i = 0; i < n; i += l << 1) {
				Z *A1 = A + i, *A2 = A + i + l, *wk = w[t].data();
				for (int j = 0; j < l; j++, A1++, A2++) {
					Z x = (*A2) * (*wk++);
					*A2 = *A1 - x;
					*A1 += x;
				}
			}
		}
		if (opt) {
			std::reverse(A + 1, A + n);
			Z invN = inv(n);
			for (int i = 0; i < n; i++) {
				A[i] *= invN;
			}
		}
	}
	inline void dft(Poly &A, int k) {
		ntt(A, k, false);
	}
	inline void idft(Poly &A, int k) {
		ntt(A, k, true);
	}
}



inline Poly operator * (const Poly &A, const Poly &B);
inline Poly operator / (const Poly &A, const Poly &B);
inline Poly operator % (const Poly &A, const Poly &B);
inline Poly operator << (const Poly &A, const int &k);
inline Poly operator >> (const Poly &A, const int &k);
inline Poly der(const Poly &A);
inline Poly itg(const Poly &A);
inline std::pair<Poly, Poly> div(const Poly &A, const Poly &B);
inline Poly inv(const Poly &A);
inline Poly sqrt(const Poly &A);
inline Poly ln(const Poly &A);
inline Poly exp(const Poly &A);
inline Poly root(const Poly &A, const int &k);
inline Poly power(const Poly &A, const int &k);
inline Poly sin(const Poly &A);
inline Poly cos(const Poly &A);
inline Poly tan(const Poly &A);
inline Poly asin(const Poly &A);
inline Poly acos(const Poly &A);
inline void print(const Poly &A, const char &mid);


inline void print(const Poly &A, const char &mid = ' ') {
	int n = A.size();
	for (int i = 0; i < n; i++) {
		printf("%u%c", A[i].v, i == n - 1 ? '\n' : mid);
	}
}

inline Poly operator * (const Poly &A, const Poly &B) {
	int n = A.size() + B.size() - 1, k = ceilLog(n), N = 1 << k;
	Poly F(A), G(B);
	F.resize(N, 0);
	G.resize(N, 0);
	NTT::dft(F, k);
	NTT::dft(G, k);
	for (int i = 0; i < N; i++) {
		F[i] *= G[i];
	}
	NTT::idft(F, k);
	F.resize(n, 0);
	return F;
}
inline Poly operator / (const Poly &A, const Poly &B) {
}
inline Poly operator % (const Poly &A, const Poly &B) {

}
inline Poly operator << (const Poly &A, const int &k) {
	int n = A.size();
	if (k >= n) {
		return Poly(n, 0);
	}
	Poly B(n, 0);
	std::copy_n(A.data(), n - k, B.data() + k);
	return B;
}
inline Poly operator >> (const Poly &A, const int &k) {
	int n = A.size();
	if (k >= n) {
		return Poly(n, 0);
	}
	Poly B(n, 0);
	std::copy_n(A.data() + k, n - k, B.data());
	return B;
}
inline Poly der(const Poly &A) {
	int n = A.size();
	Poly B(n, 0);
	for (int i = 1; i < n; i++) {
		B[i - 1] = A[i] * i;
	}
	return B;
}
inline Poly itg(const Poly &A) {
	int n = A.size();
	Poly B(n, 0);
	for (int i = 1; i < n; i++) {
		B[i] = A[i - 1] * inv(i);
	}
	return B;
}
inline std::pair<Poly, Poly> div(const Poly &A, const Poly &B) {

}
inline Poly inv(const Poly &A) {
	assert(A[0].v != 0);
	int n = A.size(), k = ceilLog(n), N = 1 << k;
	Poly I(N, 0);
	I[0] = inv(A[0]);
	for (int i = 1; i <= k; i++) {
		int n = 1 << i, N = n << 1;
		Poly P(I.begin(), I.begin() + n);
		Poly Q(A.begin(), A.begin() + n);
		P.resize(N, 0);
		Q.resize(N, 0);
		NTT::dft(P, i + 1);
		NTT::dft(Q, i + 1);
		for (int j = 0; j < N; j++) {
			P[j] *= (2 - Q[j] * P[j]);
		}
		NTT::idft(P, i + 1);
		std::copy_n(P.data(), n, I.data());
	}
	I.resize(n, 0);
	return I;
}
inline Poly sqrt(const Poly &A) {
	int n = A.size(), k = ceilLog(n), N = 1 << k;
	Poly S(N, 0);
	S[0] = degree(A[0], 2);
	for (int i = 1; i <= k; i++) {
		int n = 1 << i, N = n << 1;
		Poly P(S.data(), S.data() + n);
		Poly Q(A.data(), A.data() + n);
		Poly R = inv(P);
		P.resize(N, 0);
		Q.resize(N, 0);
		R.resize(N, 0);
		NTT::dft(P, i + 1);
		NTT::dft(Q, i + 1);
		NTT::dft(R, i + 1);
		for (int j = 0; j < N; j++) {
			P[j] = (P[j] + Q[j] * R[j]) * I2;
		}
		NTT::idft(P, i + 1);
		std::copy_n(P.data(), n, S.data());
	}
	S.resize(n, 0);
	return S;
}
inline Poly ln(const Poly &A) {
	assert(A[0].v == 1);
	return itg(slice(der(A) * inv(A), A.size()));
}
inline Poly exp(const Poly &A) {
	assert(A[0].v == 0);
	int n = A.size(), k = ceilLog(n), N = 1 << k;
	Poly E(N, 0);
	E[0] = 1;
	for (int l = 2; l <= N; l <<= 1) {
		Poly P(E.data(), E.data() + l);
		Poly Q(A.data(), A.data() + l);
		P = (Q - ln(P) + 1) * P;
		std::copy_n(P.data(), l, E.data());
	}
	E.resize(n, 0);
	return E;
	/*
	F(x) = (A(x) - ln F0(x) + 1) * F0(x) (mod x ^ n)
	*/
}
inline Poly root(const Poly &A, const int &k) {
	return k == 2 ? sqrt(A) : exp(ln(A) * inv(k));
}
inline Poly power(const Poly &A, const int &k) {
	int p = 0;
	for (; A[p].v == 0; p++);
	return (exp((A >> p) * inv(A[p]) * k) * power(A[p], k)) << (k * p);
}
inline Poly sin(const Poly &A) {
	
	// e ^ (i * A) = cos(A) + i * sin(A)
	// e ^ (i * -A) = cos(A) - i * sin(A)
}
inline Poly cos(const Poly &A) {

	// e ^ (i * A) = cos(A) + i * sin(A)
	// e ^ (i * -A) = cos(A) - i * sin(A)
}
inline Poly tan(const Poly &A) {
	
}
inline Poly asin(const Poly &A) {

}
inline Poly acos(const Poly &A) {

}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	NTT::init(ceilLog(n + m + 1));
	Poly A(n + 1), B(m + 1);
	for (auto &x : A) {
		scanf("%u", &x.v);
	}
	for (auto &x : B) {
		scanf("%u", &x.v);
	}
	print(A * B);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #138.37 us36 KBAcceptedScore: 0

Subtask #1 Testcase #267.205 ms7 MB + 1004 KBAcceptedScore: 100

Subtask #1 Testcase #331.241 ms3 MB + 592 KBAcceptedScore: 0

Subtask #1 Testcase #431.34 ms3 MB + 580 KBAcceptedScore: 0

Subtask #1 Testcase #540.38 us36 KBAcceptedScore: 0

Subtask #1 Testcase #638.57 us36 KBAcceptedScore: 0

Subtask #1 Testcase #738.52 us36 KBAcceptedScore: 0

Subtask #1 Testcase #859.169 ms7 MB + 468 KBAcceptedScore: 0

Subtask #1 Testcase #959.603 ms7 MB + 468 KBAcceptedScore: 0

Subtask #1 Testcase #1052.053 ms6 MB + 952 KBAcceptedScore: 0

Subtask #1 Testcase #1167.618 ms8 MB + 60 KBAcceptedScore: 0

Subtask #1 Testcase #1266.747 ms6 MB + 964 KBAcceptedScore: 0

Subtask #1 Testcase #1337.39 us36 KBAcceptedScore: 0

Judge Duck Online | 评测鸭在线
Server Time: 2026-03-24 16:59:42 | Loaded in 1 ms | Server Status
个人娱乐项目，仅供学习交流使用 | 捐赠