QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#118109 | #5442. Referee Without Red | hos_lyric | AC ✓ | 450ms | 111212kb | C++14 | 8.9kb | 2023-07-03 03:46:09 | 2023-07-03 03:46:12 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
constexpr int LIM_INV = 3'000'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];
void prepare() {
inv[1] = 1;
for (int i = 2; i < LIM_INV; ++i) {
inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
}
fac[0] = invFac[0] = 1;
for (int i = 1; i < LIM_INV; ++i) {
fac[i] = fac[i - 1] * i;
invFac[i] = invFac[i - 1] * inv[i];
}
}
Mint binom(Int n, Int k) {
if (n < 0) {
if (k >= 0) {
return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
} else if (n - k >= 0) {
return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
} else {
return 0;
}
} else {
if (0 <= k && k <= n) {
assert(n < LIM_INV);
return fac[n] * invFac[k] * invFac[n - k];
} else {
return 0;
}
}
}
vector<int> uf;
int root(int u) {
return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
u = root(u);
v = root(v);
if (u == v) return false;
if (uf[u] > uf[v]) swap(u, v);
uf[u] += uf[v];
uf[v] = u;
return true;
}
vector<vector<int>> decompose(int n) {
vector<int> to;
for (int u = 0; u < n; u += 2) to.push_back(u);
for (int u = 1; u < n; u += 2) to.push_back(u);
vector<vector<int>> uss;
vector<int> vis(n, 0);
for (int s = 0; s < n; ++s) if (!vis[s]) {
vector<int> us;
for (int u = s; !vis[u]; u = to[u]) {
vis[u] = 1;
us.push_back(u);
}
uss.push_back(us);
}
return uss;
}
int getPeriod(const vector<int> &as) {
const int n = as.size();
vector<int> fail(n + 1);
int j = fail[0] = -1;
for (int i = 0; i < n; ++i) {
for (; ~j && as[j] != as[i]; j = fail[j]) {}
fail[i + 1] = ++j;
}
const int per = n - fail[n];
return (n % per == 0) ? per : n;
}
/*
by row, col, row^-1, col^-1:
o
o o
generates Alt = <(1 2 3), (1 2 4), ...>
(casework)
*/
int M, N;
vector<vector<int>> A;
int main() {
prepare();
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
scanf("%d%d", &M, &N);
A.assign(M, vector<int>(N));
for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
scanf("%d", &A[x][y]);
}
const auto xss = decompose(M);
const auto yss = decompose(N);
// cerr<<xss<<" "<<yss<<endl;
const int E = xss.size();
const int F = yss.size();
Mint ans = 1;
// 1
for (int e = 0; e < E; ++e) if (xss[e].size() == 1) {
// divides order of 2 mod (N-[2|N])
Int lcm = 1;
for (int f = 0; f < F; ++f) if (yss[f].size() > 1) {
vector<int> as;
for (const int x : xss[e]) for (const int y : yss[f]) {
as.push_back(A[x][y]);
}
const Int res = getPeriod(as);
lcm = lcm / __gcd(lcm, res) * res;
}
ans *= lcm;
}
for (int f = 0; f < F; ++f) if (yss[f].size() == 1) {
// divides order of 2 mod (M-[2|M])
Int lcm = 1;
for (int e = 0; e < E; ++e) if (xss[e].size() > 1) {
vector<int> as;
for (const int x : xss[e]) for (const int y : yss[f]) {
as.push_back(A[x][y]);
}
const Int res = getPeriod(as);
lcm = lcm / __gcd(lcm, res) * res;
}
ans *= lcm;
}
// cerr<<"DONE 1: ans = "<<ans<<endl;
// >= 2
vector<vector<int>> dup(E, vector<int>(F, 0));
for (int e = 0; e < E; ++e) for (int f = 0; f < F; ++f) {
if (xss[e].size() > 1 && yss[f].size() > 1) {
vector<int> as;
for (const int x : xss[e]) for (const int y : yss[f]) {
as.push_back(A[x][y]);
}
sort(as.begin(), as.end());
const int asLen = as.size();
Mint num = fac[asLen];
for (int i = 0, j; i < asLen; i = j) {
for (j = i; j < asLen && as[i] == as[j]; ++j) {}
if (j - i >= 2) {
dup[e][f] = 1;
num *= invFac[j - i];
}
}
ans *= num;
}
}
// cerr<<"optimistic ans = "<<ans<<endl;
// cerr<<"dup = "<<dup<<endl;
vector<int> ess[2], fss[2];
for (int e = 0; e < E; ++e) if (xss[e].size() > 1) ess[xss[e].size() & 1].push_back(e);
for (int f = 0; f < F; ++f) if (yss[f].size() > 1) fss[yss[f].size() & 1].push_back(f);
// |xss[e]|: odd && |yss[e]|: odd ==> only Alt
for (const int e : ess[1]) for (const int f : fss[1]) {
if (!dup[e][f]) {
ans *= inv[2];
}
}
// |xss[e]|: odd ==> only yoko-rot changes parity
for (const int e : ess[1]) {
int cnt = 0;
for (const int f : fss[0]) if (!dup[e][f]) ++cnt;
for (int i = 1; i < cnt; ++i) ans *= inv[2];
}
// |yss[f]|: odd ==> only tate-rot changes parity
for (const int f : fss[1]) {
int cnt = 0;
for (const int e : ess[0]) if (!dup[e][f]) ++cnt;
for (int i = 1; i < cnt; ++i) ans *= inv[2];
}
// even
uf.assign(E + F, -1);
for (const int e : ess[0]) for (const int f : fss[0]) {
if (!dup[e][f]) {
if (!connect(e, E + f)) {
ans *= inv[2];
}
}
}
printf("%u\n", ans.x);
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 23ms
memory: 38800kb
input:
2 4 4 1 2 3 4 3 4 1 2 1 2 4 1 4 3 3 2 3 9 1 8 1 1 8 1 1 8 1 1 8 8 8 8 8 8 8 1 1 1 1 8 8 8 1 1 1
output:
96 6336
result:
ok 2 number(s): "96 6336"
Test #2:
score: 0
Accepted
time: 22ms
memory: 38776kb
input:
1 18 16 8 8 1 1 8 8 8 1 8 8 8 1 8 8 8 1 8 1 8 1 8 1 1 1 8 1 1 1 8 1 1 1 8 8 8 1 8 8 8 1 8 8 8 1 8 8 8 1 8 8 1 1 8 1 1 1 8 1 1 1 8 1 1 1 8 1 8 1 8 8 8 1 8 1 1 1 8 8 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 1 1 8 8 8 1 8 8 8 1 7 7 7 1 8 1 8 1 8 1 1 1 8 1 1 1 1 1 7 1 8 8 8 1 8 8 8 1 8 8 8 1 1 7 7 1 8 8 ...
output:
690561281
result:
ok 1 number(s): "690561281"
Test #3:
score: 0
Accepted
time: 386ms
memory: 38804kb
input:
71117 7 8 2868391 1228870 2892937 349733 664891 1675356 1981526 762573 2892937 2892937 664891 1228870 959280 762573 664891 959280 349733 250147 1675356 349733 349733 762573 1675356 250147 1675356 959280 664891 250147 250147 250147 2868391 959280 1675356 664891 250147 1228870 1981526 250147 2868391 2...
output:
462363428 38853786 194740086 215040 40320 322560 32456681 1166400 887214222 542386470 375765881 9 4 361590980 913481201 527607149 85428015 311271219 16 645120 557106771 388800 173057174 232068778 460990604 1 239327783 9 145293043 40098691 97370043 799392782 155415144 1 36 3991680 645120 545661527 55...
result:
ok 71117 numbers
Test #4:
score: 0
Accepted
time: 294ms
memory: 38828kb
input:
755 63 63 2320566 2175957 1897863 2154093 2551257 1353847 334243 2310922 489697 2025148 2898381 1301433 2025918 2624822 916273 446350 489697 1834347 1618696 1170954 1947467 565649 1188980 818151 2167497 604100 933579 1526487 727797 1757541 6096 437958 328396 1130316 1468846 836834 1116369 1764066 23...
output:
287964952 603855872 35995619 2358812 337581814 287964952 287964952 287964952 287964952 779896829 287964952 287964952 287964952 585654112 866781526 35995619 143982476 287964952 287964952 35995619 287964952 287964952 287964952 287964952 287964952 545250000 287964952 71991238 356745197 143982476 287964...
result:
ok 755 numbers
Test #5:
score: 0
Accepted
time: 343ms
memory: 46592kb
input:
3734 20000 67 1389602 980790 2386085 1588484 2146516 1958159 642773 1716215 8079 1390992 1759761 2249217 765459 1929585 2118921 2105012 772668 984626 547175 1431565 170214 158951 1747481 720208 2833374 1145557 935993 2380503 1866168 1786126 914416 226298 685975 2045140 2995280 2664012 2149948 123450...
output:
197365516 551326836 561392495 934386097 831902835 368564644 820576782 135908312 28978034 857802169 412595593 897725368 453922016 594795473 32568607 686163581 643980228 577320582 468537842 208135614 183185490 599452355 234405712 915650810 325429822 215832653 635537720 642480236 699742763 948160486 36...
result:
ok 3734 numbers
Test #6:
score: 0
Accepted
time: 176ms
memory: 38820kb
input:
100000 2 5 2821965 2145474 853310 2911664 2627670 675327 2311210 1625221 1157380 781808 2 5 1679375 1167880 1289337 64420 2022177 774138 352469 1425384 1116876 193830 2 5 639747 904150 1513642 308309 914801 572251 2736819 303116 1418330 487350 2 5 2319520 900918 2481864 2800242 2869240 675529 501477...
output:
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 312ms
memory: 105116kb
input:
1 1000000 3 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 ...
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 212ms
memory: 68476kb
input:
1 1019 2939 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 ...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 223ms
memory: 41988kb
input:
10 548 548 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2923742 2...
output:
1 1 1 1 1 1 1 1 1 1
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 291ms
memory: 61960kb
input:
1 3 1000000 558813 2058205 1362149 42752 2361885 1417440 1311102 811857 1138706 1783847 1211637 142286 389280 1119346 1784510 931938 1922983 2954956 1785620 1145793 458753 930368 1977062 1660051 290861 2753729 987124 892351 2273905 1411739 874366 2622789 810879 2935768 189630 224383 2232004 2454137 ...
output:
101698806
result:
ok 1 number(s): "101698806"
Test #11:
score: 0
Accepted
time: 281ms
memory: 40048kb
input:
11 4096 64 898450 1681361 2230950 1638809 238161 1410068 379732 1837721 181368 2355882 479905 784097 537776 2313161 1584151 773188 2237462 1358310 459790 2752616 798396 141810 2679370 2698278 2602077 615842 462492 2749344 2705444 2075635 454060 2793444 1507647 640998 1086593 1119845 2593790 188559 2...
output:
895768193 895768193 895768193 895768193 895768193 895768193 895768193 895768193 895768193 895768193 895768193
result:
ok 11 numbers
Test #12:
score: 0
Accepted
time: 423ms
memory: 38816kb
input:
100000 50 8 483500 1744972 1187717 1972868 1522370 450944 227590 1083486 1980954 1042582 511685 659124 692416 2107423 1133047 76837 1032839 1237403 2230725 2507416 1595357 1076885 2921597 2354241 2561186 676108 2807830 2216038 1525865 2491408 1708010 1545488 894663 173330 1316641 2754343 730961 1548...
output:
194908098 335841897 583434613 116705961 990265921 629536747 970713172 131734709 379121196 63186866 457660721 676587194 139868584 801424965 959925421 844968625 452553177 1556948 102148970 492084665 630697510 832396371 605308395 201769465 1737965 666075557 669421388 888636698 582292881 661600800 42656...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 244ms
memory: 45116kb
input:
5 2 262144 165233 1109445 1078603 2241391 1109445 2570615 2373757 2993171 1078603 582175 237908 2814220 2241391 590276 270066 188796 1109445 2673098 2252815 1040118 2570615 1153927 894338 2573075 2373757 125622 2171831 2441734 2993171 858173 1719848 870986 1078603 2550304 2856750 1362678 582175 8619...
output:
18 6 3 1 6
result:
ok 5 number(s): "18 6 3 1 6"
Test #14:
score: 0
Accepted
time: 206ms
memory: 47672kb
input:
4 2 300301 2318551 2845506 2845506 2845506 2845506 2845506 2845506 2151208 2151208 2845506 457888 2845506 2845506 2151208 457888 2845506 2845506 457888 457888 457888 2845506 2151208 457888 2845506 457888 457888 2845506 2845506 457888 2151208 2151208 457888 457888 2845506 2845506 2151208 2845506 2151...
output:
1651650 955500 27327300 1651650
result:
ok 4 number(s): "1651650 955500 27327300 1651650"
Test #15:
score: 0
Accepted
time: 279ms
memory: 70724kb
input:
1 3 963901 2947916 1643802 1371991 1371991 1643802 1371991 1371991 1643802 1643802 1371991 1371991 1643802 1371991 1643802 1643802 1371991 1643802 1371991 1643802 1371991 1371991 1371991 1371991 1643802 1643802 1371991 1643802 1643802 1643802 1643802 1371991 1643802 1371991 1371991 1371991 1643802 1...
output:
314574806
result:
ok 1 number(s): "314574806"
Test #16:
score: 0
Accepted
time: 277ms
memory: 66836kb
input:
18053 2 963902 2859316 713644 272541 1850237 210197 181665 2112644 2329446 1252516 404630 1841580 170227 57456 394318 1675297 1101609 2498887 1218500 1675297 156329 394932 12136 170227 210197 2580900 1459845 332972 2206310 170227 2454934 352025 1562019 2393431 2915495 2944071 394318 2944071 170227 1...
output:
10924200 2499000 26010000 31741956 15729156 47628 67600 884 148 32 18 9 2 2 1 2 2 2 2 2 4 1 2 2 4 2 4 2 2 2 4 2 1 2 4 1 2 4 2 4 2 2 1 1 1 2 2 4 2 1 1 2 1 2 4 2 2 1 2 4 1 2 4 2 2 4 2 1 1 2 4 2 2 4 2 1 2 2 4 1 1 4 1 1 1 1 4 1 2 4 1 4 4 1 2 4 2 1 4 4 1 2 1 4 1 4 2 1 1 4 2 1 1 2 1 1 2 2 2 2 4 4 4 1 2 2 ...
result:
ok 18053 numbers
Test #17:
score: 0
Accepted
time: 389ms
memory: 44488kb
input:
4 888 992 1467656 204183 204183 1184748 204183 204183 545206 178451 204183 204183 204183 1184748 1946171 204183 1184748 2543647 204183 1946171 204183 204183 204183 204183 545206 135069 663878 204183 204183 178451 545206 204183 1418793 204183 204183 204183 663878 2189832 204183 2189832 204183 780820 ...
output:
390586406 347232840 146066813 815812865
result:
ok 4 number(s): "390586406 347232840 146066813 815812865"
Test #18:
score: 0
Accepted
time: 288ms
memory: 45936kb
input:
3 98 7824 47447 1709740 1709740 1709740 1709740 358466 1709740 358466 1709740 1709740 358466 1709740 1709740 1709740 358466 358466 1709740 358466 1709740 1709740 358466 358466 1709740 358466 1709740 1709740 1709740 1709740 358466 1709740 358466 1709740 1709740 1709740 358466 1709740 1709740 1709740 ...
output:
431970587 292200177 290712332
result:
ok 3 number(s): "431970587 292200177 290712332"
Test #19:
score: 0
Accepted
time: 292ms
memory: 39652kb
input:
44 73 984 1300695 1456664 1456664 1456664 1456664 2676550 1456664 1456664 1456664 1456664 2676550 2676550 1456664 2676550 1456664 2676550 1456664 2676550 1456664 1456664 2676550 1456664 2676550 1456664 1456664 1456664 2676550 1456664 1456664 2676550 2676550 1456664 1456664 2676550 2676550 2676550 14...
output:
561547952 197343868 621444151 614222846 768930662 830939092 478222927 227692423 466413199 348639296 148494015 492549108 263095937 885313915 557373575 866002846 400988175 699386376 560192492 93824307 750771737 355816102 347144648 202931766 922663770 394102229 425576733 99696943 906083140 908766927 54...
result:
ok 44 numbers
Test #20:
score: 0
Accepted
time: 450ms
memory: 51092kb
input:
26826 5 333332 2271885 2301375 2301375 960487 2301375 645692 960487 2301375 2301375 645692 645692 645692 960487 2301375 2301375 2301375 2301375 645692 645692 960487 645692 960487 645692 2301375 960487 960487 2301375 2301375 2301375 2301375 2301375 2301375 2301375 2301375 645692 645692 645692 645692 ...
output:
447521657 715582340 710298984 983206333 491344344 703624258 443542944 174408885 78763554 946230891 700032934 161280 24 40320 40320 48 40320 2 161280 48 80640 40320 24 40320 80640 48 40320 40320 80640 24 80640 24 40320 40320 24 80640 161280 48 80640 80640 48 40320 24 80640 161280 24 40320 80640 24 24...
result:
ok 26826 numbers
Test #21:
score: 0
Accepted
time: 228ms
memory: 50368kb
input:
3 948 948 1195238 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 1945196 19...
output:
565311873 274004344 512126562
result:
ok 3 number(s): "565311873 274004344 512126562"
Test #22:
score: 0
Accepted
time: 227ms
memory: 38908kb
input:
563 84 68 672359 1136343 193029 476488 1170370 1807703 2843516 1324070 1201532 2116780 1920959 2070615 1460979 1713965 2792175 571684 1372586 1136470 870476 1584153 980295 1460340 2398642 1470760 1716564 47804 1708687 532702 91867 1693705 772339 297433 196239 1528376 1528376 196239 297433 772339 169...
output:
229443099 944257441 944835509 876250418 373730587 429009165 805048881 352308785 505175977 703164869 356162976 372023737 670689726 776723050 178946337 99548922 728301872 932330664 3758690 323248253 705233356 851323764 839231485 168884444 830314243 468513608 898051473 423758161 281370882 569421402 736...
result:
ok 563 numbers
Test #23:
score: 0
Accepted
time: 282ms
memory: 56652kb
input:
3019 31182 60 1323593 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 2922126 292212...
output:
397034210 677306135 885722766 135627245 211115972 190988312 460912704 92880810 944639401 727420482 172959823 80703784 201620493 138095977 157527108 528730902 775786899 853798029 13952743 631551200 78763554 105084940 883706631 854249398 441119108 415966421 289782427 812330482 324898239 812236778 2323...
result:
ok 3019 numbers
Test #24:
score: 0
Accepted
time: 323ms
memory: 54772kb
input:
7280 8 249990 1371534 1944723 1191281 2628971 1227244 1582562 1373066 1605470 2426114 717807 1270894 1471694 839954 1223016 2634835 1465519 2585658 2477686 2551100 2966060 853922 1709352 1696642 2300907 1290919 1567226 1728468 1028296 2286809 214332 2191015 1886588 47397 568009 1128610 673757 109107...
output:
191406647 9 444260603 42 717157189 1018 837167067 861948796 38314876 242160579 2 25920 1 4 3110400 3110400 48 80640 4 6 2 80640 3110400 80640 1 2160 80640 4320 2 2 3 720 2 48 1440 2160 48 518400 6 720 6 8640 2 3 2 4320 4320 2 1 720 6 2 161280 2160 2160 1555200 3 1 4320 3 1555200 48 518400 518400 806...
result:
ok 7280 numbers
Test #25:
score: 0
Accepted
time: 340ms
memory: 70508kb
input:
9500 399990 5 649760 474572 2722049 2722049 474572 230570 1396595 1122636 1122636 1122636 678400 1122636 2614592 1146968 1146968 150153 1146968 1122636 1122636 1146968 2160560 1146968 1122636 1122636 1146968 1172915 1122636 1122636 1396595 1146968 899626 1122636 1818749 1396595 1122636 90831 1122636...
output:
394470255 200584074 990778581 945378159 698980044 498287106 66205267 185693603 507878948 859532416 1120 922521600 16 24 336 12 96 12 24 56 672 4480 840 1 24 70 24 24 4 168 8 224 560 140 8 28 24 280 1120 6720 1120 672 4480 16 48 280 48 168 2240 672 20160 224 4 336 336 4 8 280 2 96 24 12 280 24 40320 ...
result:
ok 9500 numbers
Test #26:
score: 0
Accepted
time: 411ms
memory: 111212kb
input:
1 999980 3 1074243 1095278 2696967 1095278 525096 1610788 2696967 1024444 886126 1390386 1048781 423277 1095278 2081185 1747503 2696967 2282318 663113 2696967 2678416 184473 1390386 902430 1239748 2696967 2537947 759518 1095278 603898 2436050 1390386 2672049 208576 2696967 329287 2709329 1095278 616...
output:
114608972
result:
ok 1 number(s): "114608972"
Test #27:
score: 0
Accepted
time: 291ms
memory: 67836kb
input:
35 2 999980 2480848 2255438 2752487 227273 2255438 227273 1886503 1886503 227273 1886503 1886503 2752487 227273 227273 2255438 2255438 2752487 227273 2255438 2255438 227273 2752487 2752487 1886503 2752487 227273 2255438 227273 2752487 2255438 2752487 227273 2255438 2752487 227273 1886503 227273 2272...
output:
466457108 21054323 131329656 8255014 152423716 12294 268912 48841 296 13 2 1 2 1 2 1 1 2 2 2 1 2 4 2 1 2 1 1 2 2 2 1 1 2 4
result:
ok 35 numbers
Test #28:
score: 0
Accepted
time: 363ms
memory: 61892kb
input:
1 3 999719 42574 222177 2916750 2766276 51762 2598689 1945103 2640165 1396959 501354 2559406 1655642 1086803 40134 1765336 1313973 828335 1439248 489537 2405692 1296820 2947482 1655642 2277754 5233 738935 1046495 307649 429192 2625122 1313973 2683358 2439195 1851661 1439248 48606 357660 391938 16036...
output:
126184948
result:
ok 1 number(s): "126184948"
Test #29:
score: 0
Accepted
time: 291ms
memory: 38816kb
input:
2267 21 63 1960236 733461 733461 2354102 733461 1272813 2354102 2630641 733461 557007 1272813 2140393 2354102 1949982 2630641 1536610 733461 1272813 557007 1949982 1272813 851382 2140393 98243 2354102 2140393 1949982 2032547 2630641 98243 1536610 2126288 733461 2354102 1272813 2630641 557007 2140393...
output:
760703880 784608238 260962636 336343980 254041325 210638536 523903606 98372702 932023826 64725522 717802269 578627021 636673496 51424979 215832606 149455996 158358000 717802269 967266316 582733196 511841879 100564627 972435761 924149604 190505160 748548845 566282337 812376131 107782854 47789192 2543...
result:
ok 2267 numbers
Test #30:
score: 0
Accepted
time: 275ms
memory: 40004kb
input:
11 64 4096 468810 2818440 2818440 456200 2818440 515043 456200 597791 2818440 1100895 515043 360921 456200 2176600 597791 1280767 2818440 764024 1662597 747623 515043 2047254 360921 2526840 456200 486305 2176600 1639804 597791 2777554 1280767 1885765 2818440 1890682 764024 439242 284177 1826083 5103...
output:
76439836 843525235 834526888 198305736 387243705 821246311 562338181 778651589 952174889 669508680 715617511
result:
ok 11 numbers
Test #31:
score: 0
Accepted
time: 282ms
memory: 38844kb
input:
390 120 64 2158395 1288572 1288572 915754 1288572 609386 915754 2648453 1288572 2933313 609386 767479 915754 9953 2648453 2187006 1288572 609386 2933313 9953 609386 2444778 767479 2029697 915754 767479 9953 1263239 2648453 2029697 2187006 2815066 1288572 915754 609386 2648453 2933313 767479 9953 218...
output:
495910768 489487951 743866152 305412872 721512637 495910768 412894133 819786270 458634846 910299204 72601810 996103414 653620320 805326068 396422618 926043215 433786926 433260912 459731178 91620906 489487951 498051707 230456715 39571272 213619388 265456189 837591302 369974881 614194804 889046257 651...
result:
ok 390 numbers
Test #32:
score: 0
Accepted
time: 295ms
memory: 38800kb
input:
215 91 153 2299840 2329052 1138450 803548 1762133 1895911 1338856 2708977 763211 875568 218309 662998 793096 2236393 2182569 1155144 1995508 1939515 1702853 1929320 2659251 1155144 2366608 699833 963369 2416266 1853888 540779 86560 1237949 1155144 544856 2819008 1824921 1312090 1173652 875568 190005...
output:
411828018 845512427 174229162 191276680 893001240 9968880 252356623 740861400 321104489 65959633 991206367 412519839 373031971 506949602 10605093 805207564 622057262 933664529 382917976 167109277 449898557 483987902 246935029 953307162 561698023 993165090 472694796 86372194 344809834 962929286 29166...
result:
ok 215 numbers
Test #33:
score: 0
Accepted
time: 339ms
memory: 39592kb
input:
16 429 428 1464072 77033 77033 825425 77033 503374 2468139 349361 77033 567026 2007937 2539483 1330243 2280123 349361 178766 77033 503374 567026 825425 1478259 349361 2820302 567026 1058673 77033 825425 2007937 349361 567026 1106811 1478259 77033 1042438 2007937 349361 567026 567026 2468139 567026 1...
output:
977719054 984959269 434764 112182444 56800710 486699038 657194346 778083497 235408409 211429214 424164403 433340631 812422636 15193533 669617105 953835886
result:
ok 16 numbers
Test #34:
score: 0
Accepted
time: 301ms
memory: 39040kb
input:
55 232 232 628773 311183 2566811 2503553 1396767 752576 2503553 913568 724617 2500973 269436 1514312 2503553 2567744 913568 2667397 2046380 1564970 2667397 2858208 2567744 259625 1514312 533764 2503553 724617 978468 2503553 913568 1396767 1425279 1564970 311183 2556172 1564970 2361170 1425279 139676...
output:
980386806 639564639 958829087 71963383 904869170 365949680 800253080 692719008 613056109 39517549 819126252 186668804 943310633 926892314 747851986 352508203 963374271 40013989 246030755 852222467 70609469 371327348 53252472 12740712 814466211 31261549 331239441 719897931 43794568 292642658 96802734...
result:
ok 55 numbers
Test #35:
score: 0
Accepted
time: 288ms
memory: 38908kb
input:
808 32 32 2822867 1551832 1551832 1323041 1551832 2197205 1999902 2535364 1551832 371204 1216649 1285960 1628121 1536267 2535364 227264 1551832 893735 1745280 2535364 2129479 813620 1818523 227264 1996853 2535364 838763 227264 2535364 227264 227264 1310055 994555 1629933 2372712 31920 1913814 124896...
output:
693320175 538776461 53415473 289958800 103685507 622817345 196597539 627075425 538157260 104902143 105113108 774478546 257662471 326811123 529763966 586181137 305151630 345935747 513955592 3428397 70401122 36 793524489 938844378 434997673 786118623 823685736 194580420 492739362 881706634 750755917 3...
result:
ok 808 numbers
Test #36:
score: 0
Accepted
time: 289ms
memory: 45460kb
input:
3 920 954 2363799 2291609 2291609 2718015 2291609 2407353 175500 1213245 2291609 1101290 2407353 1876364 2718015 1541809 1541809 1213245 2291609 701999 1101290 2407353 2407353 1967461 1876364 192878 175500 1404932 1213245 1876364 1213245 549260 1541809 1967461 2291609 2764587 701999 1810300 1101290 ...
output:
289672439 303922735 529968322
result:
ok 3 number(s): "289672439 303922735 529968322"
Test #37:
score: 0
Accepted
time: 344ms
memory: 45728kb
input:
4 678 757 751077 868395 2831269 868395 2153779 1278026 2831269 821166 181327 868395 868395 1575224 2153779 1452377 1278026 1278026 2462765 2462765 2831269 821166 2831269 821166 1794730 2418101 181327 821166 2418101 868395 868395 2418101 868395 181327 1590140 1575224 1590140 1141288 2153779 181327 12...
output:
28634474 169500867 784033374 900518142
result:
ok 4 number(s): "28634474 169500867 784033374 900518142"
Test #38:
score: 0
Accepted
time: 281ms
memory: 61556kb
input:
2 2 749701 825691 1526359 2259012 1526359 1526359 1526359 2259012 1526359 2259012 1526359 2259012 2259012 1526359 1526359 2259012 1526359 1526359 1526359 2259012 2259012 1526359 1526359 1526359 1526359 2259012 1526359 2259012 1526359 1526359 1526359 2259012 1526359 2259012 2259012 2259012 1526359 15...
output:
38519261 38519261
result:
ok 2 number(s): "38519261 38519261"
Test #39:
score: 0
Accepted
time: 257ms
memory: 56232kb
input:
2 2 739201 581121 1206041 2214691 1206041 1206041 1206041 2214691 2214691 2214691 1206041 2214691 1206041 1206041 1206041 1206041 1206041 1206041 2214691 2214691 2214691 1206041 2214691 2214691 1206041 2214691 1206041 1206041 1206041 2214691 2214691 2214691 1206041 2214691 1206041 2214691 2214691 12...
output:
842927992 842927992
result:
ok 2 number(s): "842927992 842927992"
Test #40:
score: 0
Accepted
time: 300ms
memory: 62332kb
input:
2 2 749701 2193647 1448534 2839170 2839170 2839170 2839170 1448534 2839170 1448534 2839170 1448534 1448534 2839170 2839170 1448534 2839170 2839170 2839170 1448534 1448534 2839170 2839170 2839170 2839170 1448534 2839170 1448534 2839170 2839170 2839170 1448534 2839170 1448534 1448534 1448534 2839170 2...
output:
38519261 38519261
result:
ok 2 number(s): "38519261 38519261"
Test #41:
score: 0
Accepted
time: 325ms
memory: 90088kb
input:
2 743244 2 291556 1972636 1222510 1222510 2412252 2412252 1222510 1222510 1222510 1222510 1222510 1222510 2412252 2412252 1222510 1222510 2412252 2412252 1222510 1222510 2412252 2412252 2412252 2412252 1222510 1222510 1222510 1222510 2412252 2412252 1222510 1222510 1222510 1222510 1222510 1222510 24...
output:
210731998 210731998
result:
ok 2 number(s): "210731998 210731998"
Test #42:
score: 0
Accepted
time: 372ms
memory: 38808kb
input:
83333 6 6 2074395 14 85 86 13 2555555 32 1596044 1202723 802562 619454 6 93 478967 141283 1153844 1596044 93 92 1176581 1253023 1131483 141283 91 34 941705 211202 141283 217520 7 1444704 36 62 63 35 489390 6 6 2125959 50 68 69 47 323358 35 665761 996965 2348677 2233118 20 100 1012537 2291525 2967729...
output:
865676639 202838069 202838069 405676138 600541211 202838069 465980248 600541211 733108925 931960496 405676138 202838069 202838069 202838069 799392782 600541211 865676639 405676138 405676138 202838069 865676639 202838069 405676138 202838069 465980248 405676138 600541211 61501440 405676138 202838069 7...
result:
ok 83333 numbers
Test #43:
score: 0
Accepted
time: 352ms
memory: 38800kb
input:
83333 6 6 2793950 166691 99 100 24 2722932 14 262292 2352131 658115 2299392 48 59 2352131 1982423 34055 1610544 83 58 2850282 1846136 1610544 1788661 166752 166683 1001553 467370 1768593 1217326 47 2340249 36 92 166759 35 1926024 6 6 891649 166685 80 81 6 635964 17 2250074 364727 2742987 2240653 26 ...
output:
600541211 405676138 202838069 600541211 202838069 405676138 405676138 202838069 931960496 600541211 600541211 600541211 202838069 405676138 405676138 405676138 405676138 600541211 405676138 799392782 202838069 202838069 405676138 202838069 405676138 202838069 405676138 202838069 600541211 405676138 ...
result:
ok 83333 numbers
Test #44:
score: 0
Accepted
time: 296ms
memory: 38856kb
input:
88235 2 17 393537 47 78 25 47 26 60 60 78 78 59 60 25 47 25 78 47 2274504 33 81 30 34 30 85 85 80 80 85 85 30 34 30 80 34 2 17 573046 38 71 23 38 23 82 82 71 71 82 81 23 38 25 71 38 778463 35 100 41 34 41 75 75 102 100 75 75 41 35 41 100 35 2 17 1934529 24 81 33 24 33 66 66 81 81 66 66 33 24 33 80 2...
output:
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 ...
result:
ok 88235 numbers
Test #45:
score: 0
Accepted
time: 294ms
memory: 38800kb
input:
88235 17 2 924075 1035495 15 12 100 52 13 49 15 12 13 49 88 71 88 100074 100 52 99 52 88 71 88 71 13 48 100018 12 13 49 100 52 15 12 17 2 738262 1194848 13 33 51 81 38 29 13 33 100057 29 90 74 90 74 51 81 51 100100 89 74 90 74 38 29 13 32 38 29 51 81 13 33 17 2 85255 1742808 45 9 74 87 26 24 45 9 10...
output:
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 ...
result:
ok 88235 numbers
Test #46:
score: 0
Accepted
time: 321ms
memory: 38804kb
input:
88235 2 17 1701245 20 85 32 5 24 60 180 162 162 181 60 100025 5 32 85 20 319019 27 71 18 21 47 83 186 182 182 186 100084 47 21 17 71 27 2 17 1377355 49 59 33 100034 30 68 189 157 158 189 68 30 32 33 59 49 475132 25 96 17 29 50 70 160 170 170 160 100072 50 29 16 96 25 2 17 2447370 32 73 36 16 32 72 1...
output:
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 ...
result:
ok 88235 numbers
Test #47:
score: 0
Accepted
time: 302ms
memory: 38856kb
input:
88235 2 17 580306 17 94 11 22 44 77 174 190 189 174 77 44 200023 11 94 17 1727884 48 85 32 25 50 77 171 155 200156 171 77 50 24 32 85 48 2 17 212064 2 51 3 25 35 87 176 171 171 176 86 35 25 200005 51 2 1300713 23 98 13 42 48 71 192 180 180 200194 71 49 42 13 98 23 2 17 635656 16 88 34 200047 32 72 1...
output:
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 ...
result:
ok 88235 numbers
Test #48:
score: 0
Accepted
time: 315ms
memory: 38812kb
input:
88235 17 2 2114411 2985334 45 13 88 62 41 2 1919860 41 25 4 77 98 174 169 177 169 178 169 174 169 77 1919908 25 4 50 41 41 1 88 62 45 13 17 2 1010632 1856644 19 47 57 1919862 41 33 18 33 13 14 52 66 151 180 177 174 177 174 152 180 52 66 1919824 14 18 33 41 33 57 51 19 48 17 2 2094972 297777 4 35 91 ...
output:
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 ...
result:
ok 88235 numbers
Test #49:
score: 0
Accepted
time: 301ms
memory: 38852kb
input:
10380 17 17 682216 3 77 14 50 14 82 182 196 195 182 82 14 51 14 77 3 18 1676173 1614077 1683906 2793114 54661 1248248 1182436 222802 1126682 222802 264382 1182436 264382 2793114 222802 2376517 89 1282176 1248248 512222 1683906 950626 1725081 248555 886900 1580217 2176484 390303 1484477 1809501 14583...
output:
909160984 458357544 615722902 780611091 813734189 915587830 170281740 108047136 657506062 93784348 187568696 472672860 581367206 254335646 587321153 439752922 908169280 952116812 70338261 549887510 889427722 488923459 281353044 510845220 491434253 224859713 618136778 380666784 851927060 766267830 11...
result:
ok 10380 numbers
Test #50:
score: 0
Accepted
time: 292ms
memory: 38852kb
input:
10380 17 17 1283539 49 79 45 19 40 81 200 167 167 200 81 40 19 45 78 51 34 2089220 2662417 2662417 2089220 1360755 802745 2821571 2662417 2821571 388061 2089220 802745 388061 1360755 1360755 2662417 99 802745 388061 2662417 802745 2662417 1360755 802745 2662417 388061 2821571 2662417 2821571 802745 ...
output:
749199959 187568696 351394518 687629205 30107984 736228908 520407394 549887510 816857782 674956332 170281740 73334142 660849645 676778898 76669892 85140870 113521160 660370953 170281740 984304582 260203697 736228908 201859485 646909874 663683130 651418177 510845220 818123317 254335646 8461997 406122...
result:
ok 10380 numbers
Test #51:
score: 0
Accepted
time: 350ms
memory: 92284kb
input:
2 749701 2 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1...
output:
1 1
result:
ok 2 number(s): "1 1"
Test #52:
score: 0
Accepted
time: 281ms
memory: 61344kb
input:
2 2 749701 2056549 868637 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 2289191 22...
output:
38519261 38519261
result:
ok 2 number(s): "38519261 38519261"
Test #53:
score: 0
Accepted
time: 337ms
memory: 92364kb
input:
2 749701 2 148140 357201 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 1055201 2825309 105...
output:
38519261 38519261
result:
ok 2 number(s): "38519261 38519261"
Test #54:
score: 0
Accepted
time: 346ms
memory: 91064kb
input:
2 739201 2 157244 645305 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 79497 685673 1905686 794182 79497 685673 79497 685673 79497 685673 1905686 794182 79497 685673 79497 685673 79497 685673 79497 68567...
output:
842927992 842927992
result:
ok 2 number(s): "842927992 842927992"
Test #55:
score: 0
Accepted
time: 268ms
memory: 54084kb
input:
2 2 743244 1657857 1539570 1539570 1539570 1539570 1024631 1539570 2035284 1539570 1539570 1024631 1024631 1539570 1024631 2035284 1024631 1539570 2758838 1539570 1024631 1024631 2035284 1024631 2035284 1539570 2035284 1024631 1539570 2035284 2758838 1024631 1539570 1539570 1024631 2758838 2758838 1...
output:
210731998 210731998
result:
ok 2 number(s): "210731998 210731998"