QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128546 | #5442. Referee Without Red | Crysfly | WA | 3ms | 24828kb | C++17 | 4.4kb | 2023-07-21 10:29:49 | 2023-07-21 10:29:53 |
Judging History
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(ox.size()%2==0) hav[i]=1;
else if(oy.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: 0
Wrong Answer
time: 3ms
memory: 24828kb
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 96 6336 6336
result:
wrong answer 2nd numbers differ - expected: '6336', found: '96'