QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#863764	#9870. Items	hbbbb	WA	29ms	5860kb	C++23	22.0kb	2025-01-19 22:04:32	2025-01-19 22:04:44

Judging History

你现在查看的是最新测评结果

[2025-01-19 22:04:44]
评测

测评结果：WA
用时：29ms
内存：5860kb

查看

[2025-01-19 22:04:32]
提交

answer

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <queue>
#include <array>
#include <numeric>
using namespace std;
//#define int long long

using ll = long long;

constexpr int N = 3e5 + 5, MOD = 1e9 + 7, HSMOD = 1610612741, HSMOD2 = 998244353; // Remember to change

template<int mod> class ModInt {
public:
	// Constractor definition
	ModInt(long long v = 0) noexcept : val(v% mod) {
		if (val < 0) val += mod;
	}

	// Operator overriding
	constexpr ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
	constexpr ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
	constexpr ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
	constexpr ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
	constexpr ModInt& operator+=(const ModInt& x) {
		val += x.val;
		if (val >= mod) val -= mod;
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt& x) {
		val -= x.val;
		if (val < 0) val += mod;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt& x) {
		val *= x.val;
		val %= mod;
		if (val < 0) val += mod;
		return *this;
	}
	constexpr ModInt& operator/=(const ModInt& x) {
		long long a = mod, b = x.val;
		long long s = 1, t = 0, ns = 0, nt = 1;
		while (a % b != 0) {
			int q = a / b;
			int r = a % b;
			int tmps = s - q * ns;
			int tmpt = t - q * nt;

			a = b;
			b = r;
			s = ns;
			t = nt;
			ns = tmps;
			nt = tmpt;
		}
		val = val * nt % mod;
		if (val < 0) val += mod;
		return *this;
	}
	friend constexpr std::ostream& operator<<(std::ostream& o, const ModInt<mod>& x) {
		return o << x.val;
	}

public:
	long long val = 0;
};

using mint = ModInt<MOD>;

int mod = 998244353, grt = 3;

class poly {
private:
	std::vector<int> data;

	void out(void) {
		for (int i = 0; i < (int)data.size(); ++i) printf("%d ", data[i]);
		puts("");
	}

public:
	poly(std::size_t len = std::size_t(0)) { data = std::vector<int>(len); }

	poly(const std::vector<int>& b) { data = b; }

	poly(const poly& b) { data = b.data; }

	void resize(std::size_t len, int val = 0) { data.resize(len, val); }

	std::size_t size(void) const { return data.size(); }

	void clear(void) { data.clear(); }
#if __cplusplus >= 201103L
	void shrink_to_fit(void) { data.shrink_to_fit(); }
#endif
	int& operator[](std::size_t b) { return data[b]; }

	const int& operator[](std::size_t b) const { return data[b]; }

	poly operator*(const poly& h) const;
	poly operator*=(const poly& h);
	poly operator*(const int& h) const;
	poly operator*=(const int& h);
	poly operator+(const poly& h) const;
	poly operator+=(const poly& h);
	poly operator-(const poly& h) const;
	poly operator-=(const poly& h);
	poly operator<<(const std::size_t& b) const;
	poly operator<<=(const std::size_t& b);
	poly operator>>(const std::size_t& b) const;
	poly operator>>=(const std::size_t& b);
	poly operator/(const int& h) const;
	poly operator/=(const int& h);
	poly operator==(const poly& h) const;
	poly operator!=(const poly& h) const;
	poly operator+(const int& h) const;
	poly operator+=(const int& h);
	poly inv(void) const;
	poly inv(const int& h) const;
	friend poly sqrt(const poly& h);
	friend poly log(const poly& h);
	friend poly exp(const poly& h);
};

int qpow(int a, int b, int p = mod) {
	int res = 1;
	while (b) {
		if (b & 1) res = (ll)res * a % p;
		a = (ll)a * a % p, b >>= 1;
	}
	return res;
}

std::vector<int> rev;

void dft_for_module(std::vector<int>& f, int n, int b) {
	static std::vector<int> w;
	w.resize(n);
	for (int i = 0; i < n; ++i)
		if (i < rev[i]) std::swap(f[i], f[rev[i]]);
	for (int i = 2; i <= n; i <<= 1) {
		w[0] = 1, w[1] = qpow(grt, (mod - 1) / i);
		if (b == -1) w[1] = qpow(w[1], mod - 2);
		for (int j = 2; j < i / 2; ++j) w[j] = (ll)w[j - 1] * w[1] % mod;
		for (int j = 0; j < n; j += i)
			for (int k = 0; k < i / 2; ++k) {
				int p = f[j + k], q = (ll)f[j + k + i / 2] * w[k] % mod;
				f[j + k] = (p + q) % mod, f[j + k + i / 2] = (p - q + mod) % mod;
			}
	}
}

poly poly::operator*(const poly& h) const {
	int N = 1;
	while (N < (int)(size() + h.size() - 1)) N <<= 1;
	std::vector<int> f(this->data), g(h.data);
	f.resize(N), g.resize(N);
	rev.resize(N);
	for (int i = 0; i < N; ++i)
		rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
	dft_for_module(f, N, 1), dft_for_module(g, N, 1);
	for (int i = 0; i < N; ++i) f[i] = (ll)f[i] * g[i] % mod;
	dft_for_module(f, N, -1), f.resize(size() + h.size() - 1);
	for (int i = 0, inv = qpow(N, mod - 2); i < (int)f.size(); ++i)
		f[i] = (ll)f[i] * inv % mod;
	return f;
}

poly poly::operator*=(const poly& h) { return *this = *this * h; }

poly poly::operator*(const int& h) const {
	std::vector<int> f(this->data);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * h % mod;
	return f;
}

poly poly::operator*=(const int& h) {
	for (int i = 0; i < (int)size(); ++i) data[i] = (ll)data[i] * h % mod;
	return *this;
}

poly poly::operator+(const poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + h[i]) % mod;
	return f;
}

poly poly::operator+=(const poly& h) {
	std::vector<int>& f = this->data;
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + h[i]) % mod;
	return f;
}

poly poly::operator-(const poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] - h[i] + mod) % mod;
	return f;
}

poly poly::operator-=(const poly& h) {
	std::vector<int>& f = this->data;
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] - h[i] + mod) % mod;
	return f;
}

poly poly::operator<<(const std::size_t& b) const {
	std::vector<int> f(size() + b);
	for (int i = 0; i < (int)size(); ++i) f[i + b] = data[i];
	return f;
}

poly poly::operator<<=(const std::size_t& b) { return *this = (*this) << b; }

poly poly::operator>>(const std::size_t& b) const {
	std::vector<int> f(size() - b);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = data[i + b];
	return f;
}

poly poly::operator>>=(const std::size_t& b) { return *this = (*this) >> b; }

poly poly::operator/(const int& h) const {
	std::vector<int> f(this->data);
	int inv = qpow(h, mod - 2);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * inv % mod;
	return f;
}

poly poly::operator/=(const int& h) {
	int inv = qpow(h, mod - 2);
	for (int i = 0; i < (int)data.size(); ++i) data[i] = (ll)data[i] * inv % mod;
	return *this;
}

poly poly::inv(void) const {
	int N = 1;
	while (N < (int)(size() + size() - 1)) N <<= 1;
	std::vector<int> f(N), g(N), d(this->data);
	d.resize(N), f[0] = qpow(d[0], mod - 2);
	for (int w = 2; w < N; w <<= 1) {
		for (int i = 0; i < w; ++i) g[i] = d[i];
		rev.resize(w << 1);
		for (int i = 0; i < w * 2; ++i)
			rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? w : 0);
		dft_for_module(f, w << 1, 1), dft_for_module(g, w << 1, 1);
		for (int i = 0; i < w * 2; ++i)
			f[i] = (ll)f[i] * (2 + mod - (ll)f[i] * g[i] % mod) % mod;
		dft_for_module(f, w << 1, -1);
		for (int i = 0, inv = qpow(w << 1, mod - 2); i < w; ++i)
			f[i] = (ll)f[i] * inv % mod;
		for (int i = w; i < w * 2; ++i) f[i] = 0;
	}
	f.resize(size());
	return f;
}

poly poly::operator==(const poly& h) const {
	if (size() != h.size()) return 0;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 0;
	return 1;
}

poly poly::operator!=(const poly& h) const {
	if (size() != h.size()) return 1;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 1;
	return 0;
}

poly poly::operator+(const int& h) const {
	poly f(this->data);
	f[0] = (f[0] + h) % mod;
	return f;
}

poly poly::operator+=(const int& h) { return *this = (*this) + h; }

poly poly::inv(const int& h) const {
	poly f(*this);
	f.resize(h);
	return f.inv();
}

int modsqrt(int h, int p = mod) { return 1; }

poly sqrt(const poly& h) {
	int N = 1;
	while (N < (int)(h.size() + h.size() - 1)) N <<= 1;
	poly f(N), g(N), d(h);
	d.resize(N), f[0] = modsqrt(d[0]);
	for (int w = 2; w < N; w <<= 1) {
		g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = d[i];
		f = (f + f.inv(w) * g) / 2;
		f.resize(w);
	}
	f.resize(h.size());
	return f;
}

poly log(const poly& h) {
	poly f(h);
	for (int i = 1; i < (int)f.size(); ++i) f[i - 1] = (ll)f[i] * i % mod;
	f[f.size() - 1] = 0, f = f * h.inv(), f.resize(h.size());
	for (int i = (int)f.size() - 1; i > 0; --i)
		f[i] = (ll)f[i - 1] * qpow(i, mod - 2) % mod;
	f[0] = 0;
	return f;
}

poly exp(const poly& h) {
	int N = 1;
	while (N < (int)(h.size() + h.size() - 1)) N <<= 1;
	poly f(N), g(N), d(h);
	f[0] = 1, d.resize(N);
	for (int w = 2; w < N; w <<= 1) {
		f.resize(w), g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = d[i];
		f = f * (g + 1 - log(f));
		f.resize(w);
	}
	f.resize(h.size());
	return f;
}

struct comp {
	long double x, y;

	comp(long double _x = 0, long double _y = 0) : x(_x), y(_y) {}

	comp operator*(const comp& b) const {
		return comp(x * b.x - y * b.y, x * b.y + y * b.x);
	}

	comp operator+(const comp& b) const { return comp(x + b.x, y + b.y); }

	comp operator-(const comp& b) const { return comp(x - b.x, y - b.y); }

	comp conj(void) { return comp(x, -y); }
};

const int EPS = 1e-9;

template <typename FLOAT_T>
FLOAT_T fabs(const FLOAT_T& x) {
	return x > 0 ? x : -x;
}

template <typename FLOAT_T>
FLOAT_T sin(const FLOAT_T& x, const long double& EPS = 1e-8) {
	FLOAT_T res = 0, delt = x;
	int d = 0;
	while (fabs(delt) > EPS) {
		res += delt, ++d;
		delt *= -x * x / ((2 * d) * (2 * d + 1));
	}
	return res;
}

template <typename FLOAT_T>
FLOAT_T cos(const FLOAT_T& x, const long double& EPS = 1e-8) {
	FLOAT_T res = 0, delt = 1;
	int d = 0;
	while (fabs(delt) > EPS) {
		res += delt, ++d;
		delt *= -x * x / ((2 * d) * (2 * d - 1));
	}
	return res;
}

const long double PI = std::acos((long double)(-1));

void dft_for_complex(std::vector<comp>& f, int n, int b) {
	static std::vector<comp> w;
	w.resize(n);
	for (int i = 0; i < n; ++i)
		if (i < rev[i]) std::swap(f[i], f[rev[i]]);
	for (int i = 2; i <= n; i <<= 1) {
		w[0] = comp(1, 0), w[1] = comp(cos(2 * PI / i), b * sin(2 * PI / i));
		for (int j = 2; j < i / 2; ++j) w[j] = w[j - 1] * w[1];
		for (int j = 0; j < n; j += i)
			for (int k = 0; k < i / 2; ++k) {
				comp p = f[j + k], q = f[j + k + i / 2] * w[k];
				f[j + k] = p + q, f[j + k + i / 2] = p - q;
			}
	}
}

class arbitrary_module_poly {
private:
	std::vector<int> data;

	int construct_element(int D, ll x, ll y, ll z) const {
		x %= mod, y %= mod, z %= mod;
		return ((ll)D * D * x % mod + (ll)D * y % mod + z) % mod;
	}

public:
	int mod;

	arbitrary_module_poly(std::size_t len = std::size_t(0),
		int module_value = 1e9 + 7) {
		mod = module_value;
		data = std::vector<int>(len);
	}

	arbitrary_module_poly(const std::vector<int>& b, int module_value = 1e9 + 7) {
		mod = module_value;
		data = b;
	}

	arbitrary_module_poly(const arbitrary_module_poly& b) {
		mod = b.mod;
		data = b.data;
	}

	void resize(std::size_t len, const int& val = 0) { data.resize(len, val); }

	std::size_t size(void) const { return data.size(); }

	void clear(void) { data.clear(); }
#if __cplusplus >= 201103L
	void shrink_to_fit(void) { data.shrink_to_fit(); }
#endif
	int& operator[](std::size_t b) { return data[b]; }

	const int& operator[](std::size_t b) const { return data[b]; }

	arbitrary_module_poly operator*(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator*=(const arbitrary_module_poly& h);
	arbitrary_module_poly operator*(const int& h) const;
	arbitrary_module_poly operator*=(const int& h);
	arbitrary_module_poly operator+(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator+=(const arbitrary_module_poly& h);
	arbitrary_module_poly operator-(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator-=(const arbitrary_module_poly& h);
	arbitrary_module_poly operator<<(const std::size_t& b) const;
	arbitrary_module_poly operator<<=(const std::size_t& b);
	arbitrary_module_poly operator>>(const std::size_t& b) const;
	arbitrary_module_poly operator>>=(const std::size_t& b);
	arbitrary_module_poly operator/(const int& h) const;
	arbitrary_module_poly operator/=(const int& h);
	arbitrary_module_poly operator==(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator!=(const arbitrary_module_poly& h) const;
	arbitrary_module_poly inv(void) const;
	arbitrary_module_poly inv(const int& h) const;
	friend arbitrary_module_poly sqrt(const arbitrary_module_poly& h);
	friend arbitrary_module_poly log(const arbitrary_module_poly& h);
};

arbitrary_module_poly arbitrary_module_poly::operator*(
	const arbitrary_module_poly& h) const {
	int N = 1;
	while (N < (int)(size() + h.size() - 1)) N <<= 1;
	std::vector<comp> f(N), g(N), p(N), q(N);
	const int D = std::sqrt(mod);
	for (int i = 0; i < (int)size(); ++i)
		f[i].x = data[i] / D, f[i].y = data[i] % D;
	for (int i = 0; i < (int)h.size(); ++i) g[i].x = h[i] / D, g[i].y = h[i] % D;
	rev.resize(N);
	for (int i = 0; i < N; ++i)
		rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
	dft_for_complex(f, N, 1), dft_for_complex(g, N, 1);
	for (int i = 0; i < N; ++i) {
		p[i] = (f[i] + f[(N - i) % N].conj()) * comp(0.50, 0) * g[i];
		q[i] = (f[i] - f[(N - i) % N].conj()) * comp(0, -0.5) * g[i];
	}
	dft_for_complex(p, N, -1), dft_for_complex(q, N, -1);
	std::vector<int> r(size() + h.size() - 1);
	for (int i = 0; i < (int)r.size(); ++i)
		r[i] = construct_element(D, p[i].x / N + 0.5, (p[i].y + q[i].x) / N + 0.5,
			q[i].y / N + 0.5);
	return arbitrary_module_poly(r, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator*=(
	const arbitrary_module_poly& h) {
	return *this = *this * h;
}

arbitrary_module_poly arbitrary_module_poly::operator*(const int& h) const {
	std::vector<int> f(this->data);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * h % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator*=(const int& h) {
	for (int i = 0; i < (int)size(); ++i) data[i] = (ll)data[i] * h % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator+(
	const arbitrary_module_poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + h[i]) % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator+=(
	const arbitrary_module_poly& h) {
	if (size() < h.size()) resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) data[i] = (data[i] + h[i]) % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator-(
	const arbitrary_module_poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + mod - h[i]) % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator-=(
	const arbitrary_module_poly& h) {
	if (size() < h.size()) resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i)
		data[i] = (data[i] + mod - h[i]) % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator<<(
	const std::size_t& b) const {
	std::vector<int> f(size() + b);
	for (int i = 0; i < (int)size(); ++i) f[i + b] = data[i];
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator<<=(const std::size_t& b) {
	return *this = (*this) << b;
}

arbitrary_module_poly arbitrary_module_poly::operator>>(
	const std::size_t& b) const {
	std::vector<int> f(size() - b);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = data[i + b];
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator>>=(const std::size_t& b) {
	return *this = (*this) >> b;
}

arbitrary_module_poly arbitrary_module_poly::inv(void) const {
	int N = 1;
	while (N < (int)(size() + size() - 1)) N <<= 1;
	arbitrary_module_poly f(1, mod), g(N, mod), h(*this), f2(1, mod);
	f[0] = qpow(data[0], mod - 2, mod), h.resize(N), f2[0] = 2;
	for (int w = 2; w < N; w <<= 1) {
		g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = h[i];
		f = f * (f * g - f2) * (mod - 1);
		f.resize(w);
	}
	f.resize(size());
	return f;
}

arbitrary_module_poly arbitrary_module_poly::inv(const int& h) const {
	arbitrary_module_poly f(*this);
	f.resize(h);
	return f.inv();
}

arbitrary_module_poly arbitrary_module_poly::operator/(const int& h) const {
	int inv = qpow(h, mod - 2, mod);
	std::vector<int> f(this->data);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * inv % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator/=(const int& h) {
	int inv = qpow(h, mod - 2, mod);
	for (int i = 0; i < (int)size(); ++i) data[i] = (ll)data[i] * inv % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator==(
	const arbitrary_module_poly& h) const {
	if (size() != h.size() || mod != h.mod) return 0;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 0;
	return 1;
}

arbitrary_module_poly arbitrary_module_poly::operator!=(
	const arbitrary_module_poly& h) const {
	if (size() != h.size() || mod != h.mod) return 1;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 1;
	return 0;
}

arbitrary_module_poly sqrt(const arbitrary_module_poly& h) {
	int N = 1;
	while (N < (int)(h.size() + h.size() - 1)) N <<= 1;
	arbitrary_module_poly f(1, mod), g(N, mod), d(h);
	f[0] = modsqrt(h[0], mod), d.resize(N);
	for (int w = 2; w < N; w <<= 1) {
		g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = d[i];
		f = (f + f.inv(w) * g) / 2;
		f.resize(w);
	}
	f.resize(h.size());
	return f;
}

arbitrary_module_poly log(const arbitrary_module_poly& h) {
	arbitrary_module_poly f(h);
	for (int i = 1; i < (int)f.size(); ++i) f[i - 1] = (ll)f[i] * i % f.mod;
	f[f.size() - 1] = 0, f = f * h.inv(), f.resize(h.size());
	for (int i = (int)f.size() - 1; i > 0; --i)
		f[i] = (ll)f[i - 1] * qpow(i, f.mod - 2, f.mod) % f.mod;
	f[0] = 0;
	return f;
}

using m_poly = arbitrary_module_poly;

struct custom_hash
{
	static uint64_t splitmix64(uint64_t x) {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		return x;
	}
	size_t operator () (uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
		return splitmix64(x + FIXED_RANDOM);
	}
};

constexpr int M = 5;

struct Matrix
{
	array<array<int, M>, M> v;
	Matrix()
	{
		for (int i = 0; i < M; i++) v[i].fill(0);
	}
	void CLEAR()
	{
		for (int i = 0; i < M; i++) v[i].fill(0);
	}
	friend Matrix operator*(const Matrix& a, const Matrix& b) noexcept
	{
		Matrix c;
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < M; j++)
			{
				for (int k = 0; k < M; k++)
				{
					c.v[i][j] = (c.v[i][j] + 1ll * a.v[i][k] * b.v[k][j] % MOD) % MOD;
				}
			}
		}
		return c;
	}
};

/*
struct FastMod
{
	using ull=unsigned long long;
	using L=__int128;
	ull b,m;
	FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
	ull reduce(ull a)// return a mod b
	{
		ull q=(ull)((L(m)*a)>>64),r=a-q*b;
		return r>=b?r-b:r;
	}
}F(330); // change the MOD*/

class Union_Find
{
public:
	array<int, N> fa;
	void Init()
	{
		for (int i = 0; i < N; i++) fa[i] = i;
	}
	int find(int u)
	{
		return (fa[u] == u ? u : fa[u] = find(fa[u]));
	}
	void merge(int u, int v)
	{
		fa[find(u)] = find(v);
	}
}uf;

struct tws
{
	ll v1, v2;
	tws() = default;
	tws(ll x, ll y) :v1(x), v2(y) {}
	bool operator==(const tws x) const
	{
		return (v1 == x.v1 && v2 == x.v2);
	}
	bool operator!=(const tws x) const
	{
		return (v1 != x.v1 || v2 != x.v2);
	}
	tws operator+(const ll x)
	{
		return tws((v1 + x) % HSMOD, (v2 + x) % HSMOD2);
	}
	tws operator-(const ll x)
	{
		return tws((v1 - x + HSMOD) % HSMOD, (v2 - x + HSMOD2) % HSMOD2);
	}
	tws operator-(const tws x)
	{
		return tws((v1 - x.v1 + HSMOD) % HSMOD, (v2 - x.v2 + HSMOD2) % HSMOD2);
	}
	tws operator*(const ll x)
	{
		return tws((v1 * x) % HSMOD, (v2 * x) % HSMOD2);
	}
	tws operator+(const tws x)
	{
		return tws((v1 + x.v1) % HSMOD, (v2 + x.v2) % HSMOD2);
	}
	tws operator*(const tws x)
	{
		return tws((v1 * x.v1) % HSMOD, (v2 * x.v2) % HSMOD2);
	}
};

long long fspow(long long a, long long b)
{
	long long res = 1ll, base = a;
	while (b)
	{
		if (b & 1ll) res = res * base % MOD;
		base = base * base % MOD;
		b >>= 1ll;
	}
	return res;
}

double dist(double X0, double Y0, double X1, double Y1)
{
	return sqrt((X0 - X1) * (X0 - X1) + (Y0 - Y1) * (Y0 - Y1));
}

inline bool isprime(int x)
{
	if (x == 1) return 0;
	for (int i = 2; 1ll * i * i <= x; i++) if (x % i == 0) return 0;
	return 1;
}

int t, n;
ll m;
array<int, N> b;

int main()
{
	//freopen("*.in", "r", stdin);
	//freopen("*.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		int ec = m / n;
		for (int i = 1; i <= n; i++)
		{
			cin >> b[i];
			b[i] -= ec;
		}
		poly ve;
		ve.resize(2 * n + 1);
		for (int i = 1; i <= n; i++) ve[b[i] + n]++;
		poly res, base = ve;
		res.resize(2 * n + 1);
		res[n] = 1;
		int x = n;
		while (x)
		{
			if (x & 1)
			{
				res = res * base;
				poly nr;
				nr.resize(2 * n + 1);
				for (int i = 0; i < res.size(); i++)
				{
					int nj = i - 2 * n;
					if (nj >= -n && nj <= n) nr[nj + n] += res[i];
				}
				res = nr;
			}
			base = base * base;
			poly nr;
			nr.resize(2 * n + 1);
			for (int i = 0; i < res.size(); i++)
			{
				int nj = i - 2 * n;
				if (nj >= -n && nj <= n) nr[nj + n] += base[i];
			}
			base = nr;
			x >>= 1;
		}
		cout << (res[n + m % n] ? "Yes\n" : "No\n");
	}
	return 0;
}

/*
1
5 25
0 1 2 3 4
*/

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3712kb

input:

output:

Yes
No
No
No

result:

ok 4 token(s): yes count is 1, no count is 3

Test #2:

score: -100

Wrong Answer

time: 29ms

memory: 5860kb

input:

output:

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes...

result:

wrong answer expected YES, found NO [15th token]