結果
| 問題 | No.2291 Union Find Estimate |
| ユーザー |
 georgejsh
|
| 提出日時 | 2023-05-05 22:41:43 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,811 bytes |
| コンパイル時間 | 3,501 ms |
| コンパイル使用メモリ | 167,552 KB |
| 実行使用メモリ | 6,988 KB |
| 最終ジャッジ日時 | 2024-11-23 10:09:24 |
| 合計ジャッジ時間 | 4,534 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 13 WA * 5 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pi;
typedef pair<ld,ld> pd;
typedef vector<ll> vi;
typedef vector<ld> vd;
typedef vector<pi> vpi;
#define repab(i, a, b) for (ll i = (a); i < (b); i++)
#define repabs(i, a, b,s) for (ll i = (a); i < (b); i+=(s))
#define rep(i, a) for (ll i = 0; i < (a); i++)
#define rrepab(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define rrepabs(i,a,b,s) for (ll i = (b)-1; i >= (a); i-=(s))
#define rrep(i,a) for (ll i = (a)-1; i >= 0; i--)
#define iter(a, x) for (auto& a : x)
#define repeat(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, repabs, repab, rep)
#define F_ORRC(...) GET5(__VA_ARGS__, rrepabs, rrepab, rrep)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define FORR(...) F_ORRC(__VA_ARGS__)(__VA_ARGS__)
#define v(a) vector<array<ll,a>>
#define minheap(a) priority_queue<array<ll,a>,vector<array<ll,a>>,greater<array<ll,a>> >
#define mat(n,m) vector<vi> matrix(vi(m),n)
#define rloop(n) int n;re(n);rep(i,n)
#define array(n) array<ll,n>
#define rea(arr,n) int n;re(n);vi arr(n);re(arr);
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
namespace io {
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss);cerr<< "line: "<<__LINE__ <<" "; err(_it, args); cerr<<endl;}
void err(istream_iterator<string> it) {}
// TYPE ID (StackOverflow)
template<class T> struct like_array : is_array<T>{};
template<class T, size_t N> struct like_array<array<T,N>> : true_type{};
template<class T> struct like_array<vector<T>> : true_type{};
template<class T> bool is_like_array(const T& a) { return like_array<T>::value; }
// INPUT
template<class T> void re(T& x) { cin >> x; }
template<class Arg, class... Args> void re(Arg& first, Args&... rest);
void re(double& x) { string t; re(t); x = stod(t); }
void re(ld& x) { string t; re(t); x = stold(t); }
template<class T1, class T2> void re(pair<T1,T2>& p);
template<class T> void re(vector<T>& a);
template<class T, size_t SZ> void re(array<T,SZ>& a);
template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); }
template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.fi,p.se); }
template<class T> void re(vector<T>& a) { rep(i,sz(a)) re(a[i]); }
template<class T, size_t SZ> void re(array<T,SZ>& a) { rep(i,SZ) re(a[i]); }
template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a);
template<class T> ostream& operator<<(ostream& os, const vector<T>& a);
template<class T> ostream& operator<<(ostream& os, const set<T>& a) ;
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) ;
template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) ;
// OUTPUT
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) {
os << '{' << a.fi << ", " << a.se << '}'; return os;
}
template<class T> ostream& printArray(ostream& os, const T& a, int SZ) {
os << '{';
rep(i,SZ) {
if (i) {
os << ", ";
if (is_like_array(a[i])) os << " ";
}
os << a[i];
}
os << '}';
return os;
}
template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a) {
return printArray(os,a,SZ);
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
return printArray(os,a,sz(a));
}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {
os << vector<T>(all(a)); return os;
}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {
os << vector<T>(all(a)); return os;
}
template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {
os << vector<pair<T1,T2>>(all(a)); return os;
}
template<class T> void pr(const T& x) { cout << x << '\n'; }
template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
cout << first << ' '; pr(rest...);
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a<<" " ;
err(++it, args...);
}
template<typename T>
void pa(vector<T> &a,bool psize=true){
if(psize) cout<<a.size()<<"\n";
iter(x,a) cout<<x<<" ";
cout<<"\n";
}
}
using namespace io;
//const int MOD = 1000000007;
const int MOD = 998244353;
const ll INF = 1e18;
const int MX = 2e5+1;
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
struct FU {
std::vector<int> f, siz;
FU() {}
FU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int leader(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return leader(x) == leader(y);
}
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[leader(x)];
}
};
unsigned long long int ex(unsigned long long int a,unsigned long long int n)
{
if(n==0)
return 1;
if(n==1)
return a;
n=n%(MOD-1);
unsigned long long int y=ex(a,n/2);
if(n%2==1)
return (a*((y*y)%MOD))%MOD;
else
return (y*y)%MOD;
}
void solve(){
int w,h;re(w,h);
ll ans=1;
rep(i,w) ans=ans*10%MOD;
FU fu(w);
ll inv10=ex(10,MOD-2);
map<int,int> found;
//error(ans,inv10);
rep(i,h){
string s;re(s);
map<char,vi> mp;
rep(i,w) if(s[i]>='0' && s[i]<='9' ){
if(found.find(fu.leader(i))==found.end()){
ans=ans*inv10%MOD;
found[fu.leader(i)]=s[i];//error("here");
}else{
if(found[fu.leader(i)]!=s[i]) ans=0;
}
}else if(s[i]!='?'){
mp[s[i]].pb(i);
}
iter(x,mp){
if(sz(x.se)<=1) continue;
rep(i,sz(x.se)-1){
if(fu.merge(x.se[i],x.se[i+1])){
//error("here",x.se[i],x.se[i+1],);
if(found.find(fu.leader(x.se[i]))==found.end())
{ans=ans*inv10%MOD;}
else{
//error(found);
if(found.find(x.se[i])!=found.end() && found.find(x.se[i+1])!=found.end() && found[x.se[i]]!=found[x.se[i+1]] ) ans=0;
}
}
}
}
//error(mp,found);
iter(x,mp)
iter(y,mp) if(x.fi!=y.fi){
// if(found.find(fu.leader(x.se[0]))!=found.end() && found.find(fu.leader(y.se[0]))!=found.end() && found[fu.leader(x.se[0])]==found[fu.leader(y.se[0])] ) ans=0;
}
map<int,int> mp2;
iter(x,found) mp2[fu.leader(x.fi)]=x.se;
found=mp2;
cout<<ans<<"\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//rloop(t){
solve();
//}
return 0;
}