QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #806706 | #9870. Items | BreakPlus | WA | 14ms | 3740kb | C++14 | 12.9kb | 2024-12-09 14:15:04 | 2024-12-09 14:15:05 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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]