| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 533958 |
2022-03-07T18:04:34 Z |
AaronJ |
Set (COCI21_set) |
C++ |
|
384 ms |
21700 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <int mod> struct Fp {
int x;
Fp(int x = 0) : x(x) {}
Fp& operator+=(const Fp& other) {
if ((x += other.x) >= mod) x -= mod;
return *this;
}
Fp& operator-=(const Fp& other) {
if ((x -= other.x) < 0) x += mod;
return *this;
}
Fp& operator*=(const Fp& other) {
x = (long long)x * other.x % mod;
return *this;
}
Fp& operator/=(const Fp& other) {
return *this *= other.inv();
}
Fp operator+(const Fp& other) const {
return Fp(*this) += other;
}
Fp operator-(const Fp& other) const {
return Fp(*this) -= other;
}
Fp operator*(const Fp& other) const {
return Fp(*this) *= other;
}
Fp operator/(const Fp& other) const {
return Fp(*this) /= other;
}
Fp pow(int exp) const {
Fp ret(1), mul(*this);
while (exp > 0) {
if (exp & 1) ret *= mul;
mul *= mul;
exp >>= 1;
}
return ret;
}
Fp inv() const {
return pow(mod - 2);
}
};
template <int m> void transform(vector<Fp<m>>& f, const Fp<m> omega) {
const int n = f.size();
for (int i = 1; i < n; i *= 3) {
for (int j = 0; j < n; ++j) {
if ((j / i) % 3 == 0) {
const auto a = f[j], b = f[j + i], c = f[j + i * 2];
f[j] = a + b + c;
f[j + i] = a + b * omega + c * omega * omega;
f[j + i * 2] = a + b * omega * omega + c * omega;
}
}
}
}
template <int m, int r> vector<int> square(const vector<int>& a) {
const int n = a.size();
vector<Fp<m>> f(n);
for (int i = 0; i < n; ++i) {
f[i] = a[i];
}
const auto omega = Fp<m>(r).pow((m - 1) / 3);
transform<m>(f, omega);
for (int i = 0; i < n; ++i) {
f[i] *= f[i];
}
transform<m>(f, omega * omega);
const auto inv = Fp<m>(n).inv();
vector<int> b(n);
for (int i = 0; i < n; ++i) {
b[i] = (f[i] * inv).x;
}
return b;
}
constexpr int mod1 = 99999931;
constexpr int root1 = 2;
constexpr int mod2 = 99999043;
constexpr int root2 = 2;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, K;
std::cin >> N >> K;
vector<int> pow(K + 1);
pow[0] = 1;
for (int i = 0; i < K; ++i) {
pow[i + 1] = pow[i] * 3;
}
const int L = pow[K];
vector<int> inv(N);
vector<int> freq(L);
for (int i = 0; i < N; ++i) {
int x = 0;
for (int j = 0; j < K; ++j) {
char c;
std::cin >> c;
x += (c - '1') * pow[j];
inv[i] += (('4' - c) % 3) * pow[j];
}
freq[x] += 1;
}
const auto a = square<mod1, root1>(freq);
const auto b = square<mod2, root2>(freq);
vector<long long> c(L);
for (int i = 0; i < L; ++i) {
// x = a[i] mod M1
// x = b[i] mod M2
const int k = ((Fp<mod2>(b[i]) - Fp<mod2>(a[i])) / Fp<mod2>(mod1)).x;
c[i] = (long long)mod1 * k + a[i];
}
long long ans = 0;
for (int i = 0; i < N; ++i) {
ans += c[inv[i]];
}
std::cout << (ans - N) / 6 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
308 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
308 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
308 KB |
Output is correct |
| 19 |
Correct |
2 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
0 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
2 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
320 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
308 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
308 KB |
Output is correct |
| 19 |
Correct |
2 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
0 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
2 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
320 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
295 ms |
12692 KB |
Output is correct |
| 32 |
Correct |
284 ms |
12896 KB |
Output is correct |
| 33 |
Correct |
308 ms |
12812 KB |
Output is correct |
| 34 |
Correct |
384 ms |
21700 KB |
Output is correct |
| 35 |
Correct |
1 ms |
312 KB |
Output is correct |
| 36 |
Correct |
1 ms |
204 KB |
Output is correct |
| 37 |
Correct |
1 ms |
332 KB |
Output is correct |
| 38 |
Correct |
368 ms |
20744 KB |
Output is correct |
| 39 |
Correct |
317 ms |
14780 KB |
Output is correct |
| 40 |
Correct |
379 ms |
20580 KB |
Output is correct |
| 41 |
Correct |
304 ms |
13356 KB |
Output is correct |
| 42 |
Correct |
371 ms |
20584 KB |
Output is correct |
| 43 |
Correct |
0 ms |
204 KB |
Output is correct |
| 44 |
Correct |
1 ms |
204 KB |
Output is correct |
| 45 |
Correct |
1 ms |
312 KB |
Output is correct |
