QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#806706#9870. ItemsBreakPlusWA 14ms3740kbC++1412.9kb2024-12-09 14:15:042024-12-09 14:15:05

Judging History

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

  • [2024-12-09 14:15:05]
  • 评测
  • 测评结果：WA
  • 用时：14ms
  • 内存：3740kb
查看
  • [2024-12-09 14:15:04]
  • 提交

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 procedure(){
	n=read(),m=read(); S.t=B=m/n; int q=m-B*n;
	S.v.clear(); S.v.resize(n+1); ans.v.resize(1); ans.v[0]=1;
	// 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;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3516kb

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
No
No
No

result:

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

Test #2:

score: -100
Wrong Answer
time: 14ms
memory: 3740kb

input:

1314
1 0
0
1 0
1
1 1
0
1 1
1
2 0
0 0
2 0
0 1
2 0
0 2
2 0
1 0
2 0
1 1
2 0
1 2
2 0
2 0
2 0
2 1
2 0
2 2
2 1
0 0
2 1
0 1
2 1
0 2
2 1
1 0
2 1
1 1
2 1
1 2
2 1
2 0
2 1
2 1
2 1
2 2
2 2
0 0
2 2
0 1
2 2
0 2
2 2
1 0
2 2
1 1
2 2
1 2
2 2
2 0
2 2
2 1
2 2
2 2
2 3
0 0
2 3
0 1
2 3
0 2
2 3
1 0
2 3
1 1
2 3
1 2
2 3
2 0...

output:

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

result:

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

伺服器時間: 2025-02-01 14:01:00 | 開源專案