QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#806713#9870. ItemsBreakPlusWA 1ms3616kbC++1412.9kb2024-12-09 14:19:292024-12-09 14:19:29

Judging History

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

  • [2024-12-09 14:19:29]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3616kb
查看
  • [2024-12-09 14:19:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace Poly {
const int mod = 998244353, G = 3, GI = 332748118;

namespace math {
	mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
	uniform_int_distribution <int> uid(0, mod - 1);

	int I;

	struct Complex {
		int a, b;

		Complex() {}
		Complex(int a, int b): a(a), b(b) {}

		inline Complex operator*(const Complex &rhs) const {
			return Complex(((ll)a * rhs.a + (ll)b * rhs.b % mod * I) % mod, ((ll)a * rhs.b + (ll)b * rhs.a) % mod);
		}
	};

	inline Complex qpow(Complex a, int b) { Complex res(1, 0); while (b) {
		if (b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; }

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

	inline bool check(int a) {
		return qpow(a, (mod - 1) >> 1) != mod - 1;
	}

	inline int modsqrt(int a) {
		int b = 0;
		I = 0;
		while (check(I)) {
			b = uid(rng);
			I = ((ll)b * b - a + mod) % mod;
		}
		int res = qpow(Complex(b, 1), (mod + 1) >> 1).a;
		return min(res, mod - res);
	}
}

class poly {
private:
	vector <int> data;

public:
	inline void print(string sep = " ", string end = "\n") const {
		for (int i = 0; i < (int)data.size(); ++i) {
			cout << data[i];
			if (i != (int)data.size() - 1) {
				cout << sep;
			}
		}
		cout << end;
	}

	poly(const size_t &len = size_t(0)) { data = vector <int> (len); }
	poly(const vector <int> &a) { data = a; }

	inline void clear() { data.clear(); }
	inline void resize(const size_t &len, const int &val = 0) { data.resize(len, val); }
	inline size_t size() const { return data.size(); }

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

	inline poly operator*(const poly &h) const;
	inline poly &operator*=(const poly &h);
	inline poly operator*(const int &h) const;
	inline poly &operator*=(const int &h);
	inline poly operator/(const int &h) const;
	inline poly &operator/=(const int &h);
	inline poly operator/(const poly &h) const;
	inline poly &operator/=(const poly &h);
	inline poly operator%(const poly &h) const;
	inline poly &operator%=(const poly &h);
	inline poly operator+(const poly &h) const;
	inline poly &operator+=(const poly &h);
	inline poly operator-(const poly &h) const;
	inline poly &operator-=(const poly &h);
	inline poly operator<<(const size_t &b) const;
	inline poly &operator<<=(const size_t &b);
	inline poly operator>>(const size_t &b) const;
	inline poly &operator>>=(const size_t &b);

	inline bool operator==(const poly &h) const;
	inline bool operator!=(const poly &h) const;

	inline poly inv() const;
	inline poly inv(const size_t &b) const;
	inline poly rev() const;
	inline poly rev(const size_t &b) const;
	inline poly Der() const;
	inline poly Der(const size_t &b) const;
	inline poly Int() const;
	inline poly Int(const size_t &b) const;
	inline poly log() const;
	inline poly log(const size_t &b) const;
	inline poly exp() const;
	inline poly exp(const size_t &b) const;
	inline poly sqrt() const;
	inline poly sqrt(const size_t &b) const;
	inline poly exsqrt() const;
	inline poly exsqrt(const size_t &b) const;
	inline poly pow(const int &h) const;
	inline poly pow(const int &h, const size_t &b) const;
};

inline void addmod(int &x) { (x >= mod) && (x -= mod); }
inline int qpow(int a, int b) { int res = 1; while (b) {
	if (b & 1) { res = (ll)res * a % mod; } a = (ll)a * a % mod; b >>= 1; } return res; }
inline int qinv(int a) { return qpow(a, mod - 2); }
inline int modsqrt(int a) { return math::modsqrt(a); }

inline void NTT(vector <int> &f, int len, int g) {
	vector <int> rev(len);
	for (int i = 0; i < len; ++i) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
		if (rev[i] < i) {
			swap(f[i], f[rev[i]]);
		}
	}
	for (int i = 1; i < len; i <<= 1) {
		int wn = qpow(g, (mod - 1) / (i << 1));
		for (int j = 0; j < len; j += (i << 1)) {
			int w = 1;
			for (int k = 0; k < i; ++k) {
				int s = f[j + k], t = (ll)f[i + j + k] * w % mod;
				addmod(f[j + k] = s + t), addmod(f[i + j + k] = s - t + mod);
				w = (ll)w * wn % mod;
			}
		}
	}
}

inline poly poly::operator*(const poly &h) const {
	int len = 1;
	while (len < (int)(size() + h.size() - 1)) {
		len <<= 1;
	}
	vector <int> f(data), g(h.data);
	f.resize(len), g.resize(len);
	NTT(f, len, G), NTT(g, len, G);
	for (int i = 0; i < len; ++i) {
		f[i] = (ll)f[i] * g[i] % mod;
	}
	NTT(f, len, GI);
	int ilen = qinv(len);
	for (int i = 0; i < len; ++i) {
		f[i] = (ll)f[i] * ilen % mod;
	}
	f.resize(size() + h.size() - 1);
	return f;
}

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

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

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

inline poly poly::operator/(const int &h) const {
	int invh = qinv(h);
	vector <int> f(data);
	for (int i = 0; i < (int)size(); ++i) {
		f[i] = (ll)f[i] * invh % mod;
	}
	return f;
}

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

inline poly poly::operator/(const poly &h) const {
	if (size() < h.size()) {
		return poly();
	}
	poly res = (this -> rev() * h.rev().inv(size() - h.size() + 1));
	res.resize(size() - h.size() + 1);
	return res.rev();
}

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

inline poly poly::operator%(const poly &h) const {
	poly res = *this - *this / h * h;
	res.resize(h.size() - 1);
	return res;
}

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

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

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

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

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

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

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

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

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

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

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

inline poly poly::inv() const {
	vector <int> f, res(1);
	res[0] = qinv(data[0]);
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len << 1), res.resize(len << 1);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		NTT(f, len << 1, G);
		NTT(res, len << 1, G);
		for (int i = 0; i < (len << 1); ++i) {
			int t = (ll)f[i] * res[i] % mod * res[i] % mod;
			addmod(res[i] <<= 1);
			addmod(res[i] += mod - t);
		}
		NTT(res, len << 1, GI);
		int ilen = qinv(len << 1);
		for (int i = 0; i < len; ++i) {
			res[i] = (ll)res[i] * ilen % mod;
		}
		for (int i = len; i < (len << 1); ++i) {
			res[i] = 0;
		}
	}
	res.resize(size());
	return res;
}

inline poly poly::inv(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.inv();
}

inline poly poly::rev() const {
	vector <int> f(data);
	reverse(f.begin(), f.end());
	return f;
}

inline poly poly::rev(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.rev();
}

inline poly poly::Der() const {
	vector <int> f(size());
	for (int i = 0; i < (int)size() - 1; ++i) {
		f[i] = (ll)data[i + 1] * (i + 1) % mod;
	}
	return f;
}

inline poly poly::Der(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.Der();
}

inline poly poly::Int() const {
	vector <int> f(size());
	for (int i = 1; i < (int)size(); ++i) {
		f[i] = (ll)data[i - 1] * qinv(i) % mod;
	}
	return f;
}

inline poly poly::Int(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.Int();
}

inline poly poly::log() const {
	poly res = (Der() * inv()).Int();
	res.resize(size());
	return res;
}

inline poly poly::log(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.log();
}

inline poly poly::exp() const {
	poly f, res(1);
	res[0] = 1;
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len), res.resize(len);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		res = res - res * (res.log() - f);
		res.resize(len);
	}
	res.resize(size());
	return res;
}

inline poly poly::exp(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.exp();
}

inline poly poly::sqrt() const {
	poly f, res(1);
	res[0] = 1;
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len), res.resize(len);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		res = (f + res * res) * (res * 2).inv();
		res.resize(len);
	}
	res.resize(size());
	return res;
}

inline poly poly::sqrt(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.sqrt();
}

inline poly poly::exsqrt() const {
	poly f, res(1);
	res[0] = modsqrt(data[0]);
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len), res.resize(len);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		res = (f + res * res) * (res * 2).inv();
		res.resize(len);
	}
	res.resize(size());
	return res;
}

inline poly poly::exsqrt(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.exsqrt();
}

inline poly poly::pow(const int &h) const {
	poly f(data);
	return (f.log() * h).exp();
}

inline poly poly::pow(const int &h, const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.pow(h);
}

}

using Poly::poly;

typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
void init(){ }

ll n,m,B;
struct zhy2{
	poly v;
	int t;
	zhy2(){ }
	zhy2(poly V, int T){ v=V, t=T; }
	void limit(){
		if(t > n){
			int d = t-n;
			v >>= d;
			v.resize(2*n+1);
			t = n;
		}
	}
}S, ans;
zhy2 operator* (zhy2 A, zhy2 B){
	zhy2 T = zhy2(A.v*B.v, A.t+B.t);
	T.limit();
	return T;
}

void Resize(poly &Q, int zhy){
	Q.clear(); Q.resize(zhy);
}
void procedure(){
	n=read(),m=read();
	int q=m-B*n;
	Resize(S.v, n+1);
	Resize(ans.v, 1);
	S.t=B=m/n;
	ans.v[0]=1; ans.t=0;
	// cout<<"ok"<<endl;
	for(int i=1;i<=n;i++){
		int w=read();
		S.v[w]=1;
		// cout<<"ok"<<endl;
	}

	// cout<<"solved"<<endl;

	while(n){
		if(n&1){
			ans=ans*S;
			// for(int i=0; i<ans.v.size(); i++){
			// 	cout<<i-ans.t<<" get "<<ans.v[i]<<endl;
			// }
			// cout<<endl;
		}
		S=S*S;
		n>>=1;
	}

	// for(int i=0; i<ans.v.size(); i++){
	// 	cout<<i-ans.t<<" get "<<ans.v[i]<<endl;
	// }
	// cout<<endl;
	puts(ans.v[ans.t+q]?"Yes":"No");
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=read();
	init();
	while(T--) procedure();
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3616kb

input:

4
5 25
0 0 0 0 5
5 11
4 4 4 5 5
5 0
1 2 3 4 5
5 25
0 1 2 3 4

output:

Yes
Yes
Yes
Yes

result:

wrong answer expected NO, found YES [2nd token]
English 繁體中文 简体中文

Server Time: 2025-02-01 14:07:53 | OpenSource Project