QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#529208#6399. Classic: Classical ProblemOneWanWA 0ms3652kbC++238.8kb2024-08-24 10:30:432024-08-24 10:30:44

Judging History

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

  • [2024-08-24 10:30:44]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3652kb
查看
  • [2024-08-24 10:30:43]
  • 提交

answer

//  ██████╗ ███╗   ██╗███████╗██╗    ██╗ █████╗ ███╗   ██╗
// ██╔═══██╗████╗  ██║██╔════╝██║    ██║██╔══██╗████╗  ██║
// ██║   ██║██╔██╗ ██║█████╗  ██║ █╗ ██║███████║██╔██╗ ██║
// ██║   ██║██║╚██╗██║██╔══╝  ██║███╗██║██╔══██║██║╚██╗██║
// ╚██████╔╝██║ ╚████║███████╗╚███╔███╔╝██║  ██║██║ ╚████║
//  ╚═════╝ ╚═╝  ╚═══╝╚══════╝ ╚══╝╚══╝ ╚═╝  ╚═╝╚═╝  ╚═══╝
                                                     
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	return 0;
}();
using i64 = long long;
using Int = int;
using Long = i64;
const Long P = 998244353;
const int LEN2 = 20;
const Long NTT_G = 3; // P 的原根
const Long NTT_I = 86583718; // 根号 P - 1
Long qpow(Long a, Long b) {
    Long res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
Long qpow(Long a, Long b, const Long P) {
    Long res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
Int add(Int a, const Int b) {
    a += b;
    if (a >= P) {
        a -= P;
    }
    return a;
}
Int add(Int a, const Int b, const Int P) {
    a += b;
    if (a >= P) {
        a -= P;
    }
    return a;
}
Int sub(Int a, const Int b) {
    a -= b;
    if (a < 0) {
        a += P;
    }
    return a;
}
Int sub(Int a, const Int b, const Int P) {
    a -= b;
    if (a < 0) {
        a += P;
    }
    return a;
}
template<typename T>
struct Poly : vector<T> {
    Poly() = default;
    Poly(int n) : vector<T>(n) {}
    Poly(int n, T x) : vector<T>(n, x) {}
    Poly(vector<T>::iterator s, vector<T>::iterator t) : vector<T>(s, t) {}
    Poly(vector<T>::const_iterator s, vector<T>::const_iterator t) : vector<T>(s, t) {}
    Poly(initializer_list<T> lst) : vector<T>(lst) {}
};
namespace Polynomial {
    int norm(int x) {
        return 1 << (__lg(x - 1) + 1);
    }
    template<typename T>
    void norm(Poly<T> &a) {
        assert(!a.empty());
        a.resize(norm(a.size()));
    }
    Poly<Int> operator*(Poly<Int> a, Int b) {
        for (auto &x : a) {
            x = Long(x) * b % P;
        }
        return a;
    }
    Poly<Int> operator-(Poly<Int> a, Poly<Int> b) {
        int n = max(a.size(), b.size());
        a.resize(n);
        for (int i = 0 ; i < n ; i++) {
            a[i] = sub(a[i], b[i]);
        }
        return a;
    }
    Poly<Int> operator-(Poly<Int> a) {
        int n = a.size();
        for (int i = 0 ; i < n ; i++) {
            a[i] = sub(0, a[i]);
        }
        return a;
    }
    Poly<Int> operator+(Poly<Int> a, Poly<Int> b) {
        int n = max(a.size(), b.size());
        a.resize(n);
        for (int i = 0 ; i < n ; i++) {
            a[i] = add(a[i], b[i]);
        }
        return a;
    }
    template<typename T>
    istream& operator>>(istream &in, Poly<T> &x) {
        for (auto &x : x) {
            in >> x;
        }
        return in;
    }
    template<typename T>
    ostream& operator<<(ostream &out, const Poly<T> &x) {
        for (auto &x : x) {
            out << x << " ";
        }
        return out;
    }
}
using namespace Polynomial;
namespace NTT {
    const Long g = NTT_G; // P 的原根
    const Long I = NTT_I; // 根号 P - 1
    Poly<Long> W;
    void DIF(Int *a, int n) {
        if (W.empty()) {
            int L = 1 << LEN2;
            W.resize(L);
            Int wn = qpow(g, P / L);
            W[L >> 1] = 1;
            for (int i = L / 2 + 1 ; i < L ; i++) {
                W[i] = Long(W[i - 1]) * wn % P;
            }
            for (int i = L / 2 - 1 ; i >= 1 ; i--) {
                W[i] = W[i << 1];
            }
        }
        for (int k = n >> 1 ; k ; k >>= 1) {
            for (int i = 0 ; i < n ; i += k << 1) {
                for (int j = 0 ; j < k ; j++) {
                    Int x = a[i + j], y = a[i + j + k];
                    a[i + j] = add(a[i + j], y);
                    a[i + j + k] = Long(sub(x, y)) * W[j + k] % P;
                }
            }
        }
    }
    void IDIT(Int *a, int n) {
        for (int k = 1 ; k < n ; k <<= 1) {
            for (int i = 0 ; i < n ; i += k << 1) {
                for (int j = 0 ; j < k ; j++) {
                    Int x = a[i + j], y = Long(a[i + j + k]) * W[j + k] % P;
                    a[i + j] = add(x, y);
                    a[i + j + k] = sub(x, y);
                }
            }
        }
        Int inv = P - (P - 1) / n;
        for (int i = 0 ; i < n ; i++) {
            a[i] = Long(a[i]) * inv % P;
        }
        reverse(a + 1, a + n);
    }
}
namespace Polynomial {
    void DIF(Poly<Int> &a) {
        NTT::DIF(a.data(), a.size());
    }
    void IDIT(Poly<Int> &a) {
        NTT::IDIT(a.data(), a.size());
    }
    void dot(Poly<Int> &a, Poly<Int> &b) {
        for (int i = 0 ; i < (int) a.size() ; i++) {
            a[i] = Long(a[i]) * b[i] % P;
        }
    }
    Poly<Int> operator*(Poly<Int> a, Poly<Int> b) {
        int n = a.size() + b.size() - 1;
        if (a.size() <= 16 || b.size() <= 16) {
            Poly<Int> c(n);
            for (int i = 0 ; i < (int) a.size() ; i++) {
                for (int j =  0; j < (int) b.size() ; j++) {
                    c[i + j] = add(c[i + j], Long(a[i]) * b[j] % P);
                }
            }
            return c;
        }
        int L = norm(n);
        a.resize(L); b.resize(L);
        DIF(a); DIF(b); dot(a, b); IDIT(a);
        return a.resize(n), a;
    }
}
i64 eulerPhi(i64 n) {
    i64 ans = n;
    for (int i = 2 ; 1LL * i * i <= n ; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        ans = ans / n * (n - 1);
    }
    return ans;
}
vector<i64> getFactors(i64 x) {
    vector<i64> res;
    for (int i = 1 ; 1LL * i * i <= x ; i++) {
        if (x % i == 0) {
            res.emplace_back(i);
            if (x != 1LL * i * i) {
                res.emplace_back(x / i);
            }
        }
    }
    if (x > 1) {
        res.push_back(x);
    }
    return res;
}
i64 getMinRoot(i64 x) {
    i64 phi = eulerPhi(x);
    auto factors = getFactors(phi);
    for (int i = 1 ; ; i++) {
        if (__gcd(1LL * i, x) != 1) {
            continue;
        }
        bool flag = true;
        for (auto &e : factors) {
            if (e != phi && qpow(i, e, x) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) return i;
    }
}
void solve() {
	int n, p;
	cin >> n >> p;
	int G = getMinRoot(p);
	vector<int> a(n);
	bool flag = false;
	for (int i = 0 ; i < n ; i++) {
		cin >> a[i];
		if (a[i] == 0) {
			flag = true;
		}
	}
	if (flag == false) {
		cout << "1 1\n0\n";
		return;
	}
	if (flag == true && n == 1) {
		cout << p << " " << 1 << "\n";
		for (int i = 0 ; i < p ; i++) {
			cout << i << " ";
		}
		cout << "\n";
		return;
	}
	vector<int> f(p), g(p);
	g[0] = 1;
	for (int i = 1 ; i < p ; i++) {
		g[i] = g[i - 1] * G % p;
		f[g[i]] = i;
	}
	auto check = [&](int mid) {
		Poly<Int> h(p), w(p);
		for (int i = 1 ; i < mid ; i++) {
			h[f[i]] = 1;
		}
		for (int i = 0 ; i < n ; i++) {
			if (a[i] != 0) {
				w[p - f[a[i]]] = 1;
			}
		}
		h = h * w; h.resize(2 * p);
		for (int i = 1 ; i < p ; i++) {
			if (h[i + p] >= mid - 1) {
				return true;
			}
		}
		return false;
	};
	int L = 1, R = n + 1;
	while (L < R) {
		int mid = L + R + 1 >> 1;
		if (check(mid)) {
			L = mid;
		} else {
			R = mid - 1;
		}
	}
	vector<int> ans;
	{
		
		Poly<Int> h(p), w(p);
		for (int i = 1 ; i < L ; i++) {
			h[f[i]] = 1;
		}
		for (int i = 0 ; i < n ; i++) {
			if (a[i] != 0) {
				w[p - f[a[i]]] = 1;
			}
		}
		h = h * w; h.resize(2 * p);
		for (int i = 1 ; i < p ; i++) {
			if (h[i + p] >= L - 1) {
				ans.push_back(g[i]);
			}
		}
	}
	sort(begin(ans), end(ans));
	cout << ans.size() << " " << L << "\n";
	for (auto &x : ans) {
		cout << x << " ";
	}
	cout << "\n";
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
2 3
0 2
3 5
2 3 4
3 5
0 2 3

output:

1 2
2 
1 1
0
2 2
2 3

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3652kb

input:

3
1 2
0
1 2
1
2 2
1 0

output:

2 1
0 1 
1 1
0
1 1
1

result:

wrong answer 5th lines differ - expected: '1 2', found: '1 1'
English 繁體中文 简体中文

Server Time: 2025-02-02 00:49:02 | OpenSource Project