QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128543#5442. Referee Without RedCrysflyWA 213ms35160kbC++174.0kb2023-07-21 10:13:422023-07-21 10:13:43

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:13:43]
  • 评测
  • 测评结果:WA
  • 用时:213ms
  • 内存:35160kb
  • [2023-07-21 10:13:42]
  • 提交

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 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()
{
	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;
	}
	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);
					if(oy.size()%2) hav[n+j]=1;
					if(ox.size()%2) hav[i]=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];
	}
	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);
	int T=read();
	while(T--)work();
	return 0;
}
/*
7 5
2
4 1
15 7
*/

詳細信息

Test #1:

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

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: 8ms
memory: 24844kb

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: -100
Wrong Answer
time: 213ms
memory: 35160kb

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
718367389
460990604
1
239327783
9
145293043
40098691
97370043
799392782
155415144
1
36
3991680
645120
545661527
55...

result:

wrong answer 24th numbers differ - expected: '232068778', found: '718367389'