QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387253 | #5107. Mosaic Browsing | ucup-team1209# | WA | 90ms | 41048kb | C++20 | 3.4kb | 2024-04-12 11:05:52 | 2024-04-12 11:05:53 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 2048;
int rev[N], wn[N], lim, invlim;
int pow(int a, int b, int ans = 1) {
for(;b;b >>= 1, a = (u64) a * a % mod) if(b & 1)
ans = (u64) ans * a % mod;
return ans;
}
void init(int len) {
lim = 2 << std::__lg(len - 1);
invlim = mod - (mod - 1) / lim;
for(static int i= 1;i < lim;i += i) {
wn[i] = 1;
const int w = pow(3, mod / 2 / i);
for(int j = 1;j < i;++j) {
wn[i + j] = (u64) wn[i + j - 1] * w % mod;
}
}
for(int i = 1;i < lim;++i) {
rev[i] = rev[i >> 1] >> 1 | (i % 2u * lim / 2);
}
}
void DFT(int * a) {
static u64 t[N];
for(int i = 0;i < lim;++i) t[i] = a[rev[i]];
for(int i = 1;i < lim;i += i) {
for(int j = 0;j < lim;j += i + i) {
for(int k = 0;k < i;++k) {
const u64 x = t[i + j + k] * wn[i + k] % mod;
t[i + j + k] = t[k + j] + (mod - x), t[k + j] += x;
}
}
}
for(int i = 0;i < lim;++i) a[i] = t[i] % mod;
}
void IDFT(int * a) {
DFT(a), std::reverse(a + 1, a + lim);
for(int i = 0;i < lim;++i) {
a[i] = (u64) a[i] * invlim % mod;
}
}
int a, b, n, m;
int A[N][N];
int B[N][N];
std::mt19937_64 gen(19284124);
int mp[10000];
void solve() {
init(std::max(a + n, b + m) + 2);
static int a[N][N];
static int b[N][N];
static int sa[N][N];
static int sb[N][N];
for(int i = 0;i < lim;++i) {
for(int j = 0;j < lim;++j) {
a[i][j] = (u64) A[i][j] * A[i][j] % mod;
b[i][j] = B[i][j];
sa[i][j] = (u64) a[i][j] * A[i][j] % mod;
sb[i][j] = (u64) A[i][j] * B[i][j] % mod * B[i][j] % mod;
}
}
for(int i = 0;i < lim;++i) {
for(int j = 1;j < lim;++j) {
sa[i][j] = (sa[i][j] + sa[i][j - 1]) % mod;
sb[i][j] = (sb[i][j] + sb[i][j - 1]) % mod;
}
}
for(int i = 1;i < lim;++i) {
for(int j = 0;j < lim;++j) {
sa[i][j] = (sa[i][j] + sa[i - 1][j]) % mod;
sb[i][j] = (sb[i][j] + sb[i - 1][j]) % mod;
}
}
for(int i = 0;i < lim;++i) {
DFT(a[i]);
DFT(b[i]);
}
for(int j = 0;j < lim;++j) {
static int tmp[N];
for(int i = 0;i < lim;++i) tmp[i] = a[i][j];
DFT(tmp);
for(int i = 0;i < lim;++i) a[i][j] = tmp[i];
for(int i = 0;i < lim;++i) tmp[i] = b[i][j];
DFT(tmp);
for(int i = 0;i < lim;++i) b[i][j] = tmp[i];
}
for(int i = 0;i < lim;++i) {
for(int j = 0;j < lim;++j) {
a[i][j] = (u64) b[i][j] * a[i][j] % mod;
}
}
for(int i = 0;i < lim;++i) {
IDFT(a[i]);
}
for(int j = 0;j < lim;++j) {
static int tmp[N];
for(int i = 0;i < lim;++i) tmp[i] = a[i][j];
IDFT(tmp);
for(int i = 0;i < lim;++i) a[i][j] = tmp[i];
}
std::vector<std::pair<int, int>> v;
for(int i = ::a - 1;i < n;++i) {
for(int j = ::b - 1;j < m;++j) {
u64 ans = sa[i][j] + sb[i][j];
ans = (ans + a[i][j] * u64(mod - 2)) % mod;
if(ans == 0) {
v.emplace_back(i - ::a + 2, j - ::b + 2);
}
}
}
cout << v.size() << '\n';
for(auto [u, v] : v) {
cout << u << ' ' << v << '\n';
}
}
int main() {
for(int i = 1;i <= 100;++i) mp[i] = gen() % mod;
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> a >> b;
for(int i = 0;i < a;++i) {
for(int j = 0;j < b;++j) {
int x; cin >> x;
A[a - i - 1][b - j - 1] = mp[x];
}
}
cin >> n >> m;
for(int i = 0;i < n;++i) {
for(int j = 0;j < m;++j) {
cin >> B[i][j];
B[i][j] = mp[B[i][j]];
}
}
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 90ms
memory: 41048kb
input:
100 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
0
result:
wrong answer 1st lines differ - expected: '2005', found: '0'