結果
問題 | No.2291 Union Find Estimate |
ユーザー |
![]() |
提出日時 | 2024-04-09 11:37:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,808 bytes |
コンパイル時間 | 2,341 ms |
コンパイル使用メモリ | 206,080 KB |
最終ジャッジ日時 | 2025-02-20 23:19:08 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/dsu>#include <atcoder/modint>using namespace std;using namespace atcoder;using mint = atcoder::modint998244353;void fast_io() {ios_base::sync_with_stdio(false);cin.tie(nullptr);}int main() {fast_io();int h, w;cin >> h >> w;mint ans = mint(10).pow(h);mint inv_10 = mint(10).inv();dsu uf(h);string pw(h, '.');for (int i = 0; i < w; i++) {string s;cin >> s;vector<vector<int>> idx(26);for (int j = 0; j < h; j++) {if (s[j] == '?') {continue;} else if ('0' <= s[j] && s[j] <= '9') {if (pw[uf.leader(j)] == '.') {pw[uf.leader(j)] = s[j];ans *= inv_10;} else if (pw[uf.leader(j)] != s[j]) {ans = 0;}} else {idx[s[j] - 'a'].push_back(j);}}for (int j = 0; j < 26; j++) {for (int k = 0; k + 1 < idx[j].size(); k++) {int u = uf.leader(idx[j][k]), v = uf.leader(idx[j][k + 1]);if (uf.same(u, v)) {continue;}if (pw[u] == '.' && pw[v] == '.') {uf.merge(u, v);ans *= inv_10;} else if (pw[u] == '.') {pw[u] = pw[v];ans *= inv_10;} else if (pw[v] == '.') {pw[v] = pw[u];ans *= inv_10;} else if (pw[u] != pw[v]) {ans = 0;} else {uf.merge(u, v);}}}cout << ans.val() << "\n";}}