QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387253#5107. Mosaic Browsingucup-team1209#WA 90ms41048kbC++203.4kb2024-04-12 11:05:522024-04-12 11:05:53

Judging History

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

  • [2024-04-12 11:05:53]
  • 评测
  • 测评结果:WA
  • 用时:90ms
  • 内存:41048kb
  • [2024-04-12 11:05:52]
  • 提交

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'