QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128548#5442. Referee Without RedCrysflyRE 242ms145724kbC++174.4kb2023-07-21 10:30:442023-07-21 10:30:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 10:30:48]
  • 评测
  • 测评结果:RE
  • 用时:242ms
  • 内存:145724kb
  • [2023-07-21 10:30:44]
  • 提交

answer

// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 998244353 
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ull*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 3000005
#define inf 0x3f3f3f3f

int T,n,m,fa[maxn];
vector<vector<int>>a,vis;
long long lc[maxn];

int gf(int x){
	while(x^fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
int cnt[maxn],hav[maxn];

int nxt[maxn];
int period(vi s){
	int n=s.size(); nxt[1]=0;
	int j=0;
	For(i,1,n-1){
		while(j&&s[j]!=s[i])j=nxt[j];
		if(s[j]==s[i])++j; nxt[i+1]=j;
	}
	int d=n-nxt[n];
	if(n%d==0)return d;
	else return n;
}
int sz[maxn];

void work(int O)
{
	n=read(),m=read();
	a.resize(n),vis.resize(n);
	For(i,0,n-1){
		a[i].resize(m);
		vis[i].resize(m);
		For(j,0,m-1)a[i][j]=read(),vis[i][j]=0;
	}
//	if(O==24){
//		int tot=0;
//		For(i,0,n-1){
//			For(j,0,m-1){
//				if(!cnt[a[i][j]])cnt[a[i][j]]=++tot;
//				cout<<cnt[a[i][j]]<<" \n"[j==m-1];
//			}
//		}
//	}
//	if(T>70000)return;
	For(i,0,n+m-1)fa[i]=i,lc[i]=1,hav[i]=0,sz[i]=0;
	modint res=1;
	For(i,0,n-1)
		For(j,0,m-1){
			if(vis[i][j])continue;
			int x=i,y=j;
			vi ox,oy;
			while(!vis[x][y]){
				vis[x][y]=1,ox.pb(x);
				x=(x%2==0?x/2:x/2+(n+1)/2);
			}
			x=i,y=j,vis[x][y]=0;
			while(!vis[x][y]){
				vis[x][y]=1,oy.pb(y);
				y=(y%2==0?y/2:y/2+(m+1)/2);
			}
			for(int x:ox)for(int y:oy)vis[x][y]=1;
			if(ox.size()>1 && oy.size()>1){
				bool bo=1;
				for(int x:ox)
					for(int y:oy){
						++cnt[a[x][y]];
						res*=iv[cnt[a[x][y]]];
						if(cnt[a[x][y]]>1)bo=0; 
					}
				res*=fac[ox.size()*oy.size()];
				if(bo){
					res*=((mod+1)/2);
					if(ox.size()%2==0 && oy.size()%2==0) fa[gf(i)]=gf(n+j);
					else if(oy.size()%2==0) hav[i]=1;
					else if(ox.size()%2==0) hav[n+j]=1;
				}
				for(int x:ox)
					for(int y:oy)
						cnt[a[x][y]]=0; 
			}
			else if(ox.size()>1 || oy.size()>1){
				vi s; int u;
				if(ox.size()>1){
					u=n+j;
					for(int x:ox) s.pb(a[x][j]);
				}else{
					u=i;
					for(int x:oy) s.pb(a[i][x]);
				}
				long long len=period(s);
				lc[u]=lc[u]/__gcd(lc[u],len)*len;
			}
		}
	For(i,0,n+m-1){
		lc[i]%=mod;
		res*=lc[i];
		hav[gf(i)]|=hav[i];
	}
//	cout<<res.x<<"\n";
	For(i,0,n+m-1) sz[gf(i)]++;
	For(i,0,n+m-1)
		if(gf(i)==i){
			res*=qpow(2,sz[i]-(!hav[i]));
			sz[i]=0;
		}
	cout<<res.x<<"\n"; 
}

signed main()
{
	initC(1000005);
	T=read();
	For(_,1,T)work(_);
	return 0;
}
/*
1
8 8
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
32 41 42 43 44 45 44 46
8 47 48 49 50 51 52 53
23 54 4 55 56 57 58 59

*/

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 24784kb

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: 12ms
memory: 24872kb

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: 211ms
memory: 33408kb

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: 156ms
memory: 33112kb

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: 167ms
memory: 47640kb

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: 91ms
memory: 22816kb

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: 242ms
memory: 145724kb

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: -100
Runtime Error

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:


result: