QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128547 | #5442. Referee Without Red | Crysfly | WA | 224ms | 33416kb | C++17 | 4.4kb | 2023-07-21 10:30:09 | 2023-07-21 10:30:11 |
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: 100
Accepted
time: 8ms
memory: 24844kb
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: 7ms
memory: 24940kb
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: 224ms
memory: 33416kb
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 618786068 9 571768698 40098691 97370043 799392782 155415144 1 36 3991680 645120 545661527 55...
result:
wrong answer 27th numbers differ - expected: '239327783', found: '618786068'