QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128545#5442. Referee Without RedCrysflyWA 75ms24852kbC++174.2kb2023-07-21 10:24:312023-07-21 10:24:32

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:24:32]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:24852kb
  • [2023-07-21 10:24:31]
  • 提交

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);
					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);
	T=read();
	For(_,1,T)work(_);
	return 0;
}
/*
7 5
2
4 1
15 7
*/

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
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: 8ms
memory: 24852kb

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: 75ms
memory: 17024kb

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:

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

result:

wrong answer 1st numbers differ - expected: '462363428', found: '1'