QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128548 | #5442. Referee Without Red | Crysfly | RE | 242ms | 145724kb | C++17 | 4.4kb | 2023-07-21 10:30:44 | 2023-07-21 10:30:48 |
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(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 ...