QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#738110#5442. Referee Without RedhewanyingWA 283ms81020kbC++143.7kb2024-11-12 17:45:572024-11-12 17:46:04

Judging History

你现在查看的是最新测评结果

  • [2024-11-12 17:46:04]
  • 评测
  • 测评结果:WA
  • 用时:283ms
  • 内存:81020kb
  • [2024-11-12 17:45:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=1e6+5,H=998244353;
int n,m,a[N],p[N],q[N],fac[N],ifac[N],cn,cm,ans,res,fa[N],prm[N],cnt=0,ct[N],kmp[N],inv[N];
vector<int> vn[N],vm[N];
bool vis[N];

int adc(int a,int b){return a+b>=H?a+b-H:a+b;}
int dec(int a,int b){return a<b?a-b+H:a-b;}
int mul(int a,int b){return 1ll*a*b%H;}
void add(int &a,int b){a=adc(a,b);}
void del(int &a,int b){a=dec(a,b);}

int qpow(int a,int b=H-2){
  int res=1;
  while(b){if(b&1) res=mul(res,a);a=mul(a,a),b>>=1;}
  return res;
}

void init(){
  fac[0]=inv[1]=1;
  for(int i=2;i<N;i++) inv[i]=mul(H-H/i,inv[H%i]);
  for(int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
  ifac[N-1]=qpow(fac[N-1]);
  for(int i=N-1;i>=1;i--) ifac[i-1]=mul(ifac[i],i);
  
  for(int i=2;i<N;i++){
    if(!vis[i]) prm[++cnt]=i;
    for(int j=1;j<=cnt&&i*prm[j]<N;j++){
      vis[i*prm[j]]=1;
      if(i%prm[j]==0) break;
    }
  }
}

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

int id(int x,int y){return (x-1)*m+y;}

bool merge(int u,int v){
  u=find(u),v=find(v);
  if(u==v) return false;
  return fa[v]=u,true;
}

int calc(vector<int> &V){
  int len=(int)V.size();
  if(len==1) return 1;
  kmp[1]=0;
  for(int i=2,j=0;i<=len;i++){
    while(j&&V[i-1]!=V[j]) j=kmp[j];
    if(V[i-1]==V[j]) ++j;
    kmp[i]=j;
  }
  
  int x=kmp[len];
  while(len%(len-x)) x=kmp[x];
  
  return len-x;
}

int LCM(vector<int> &V){
  if(!(int)V.size()) return 1;

  sort(V.begin(),V.end());
  for(int i=1;i<=cnt&&prm[i]<=V.back();i++) ct[i]=0;
  
  for(auto y:V){
    int x=y;
    for(int i=1;i<=cnt&&prm[i]<=y;i++) if(x%prm[i]==0){
      int nw=0;
      while(x%prm[i]==0) ++nw,x/=prm[i];
      ct[i]=max(ct[i],nw);
    }
  }
  
  int ret=1;
  for(int i=1;i<=cnt&&prm[i]<=V.back();i++) ret=mul(ret,qpow(prm[i],ct[i]));
  return ret;
}

void SOLVE(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) p[i]=2*i-1<=n?2*i-1:(i-(n+1)/2)*2,vn[i].clear();
  for(int i=1;i<=m;i++) q[i]=2*i-1<=m?2*i-1:(i-(m+1)/2)*2,vm[i].clear();
  cn=cm=0;
  
  for(int i=1;i<=n;i++) vis[i]=false;
  for(int i=1,x;i<=n;i++) if(!vis[i]){
    ++cn,x=i;
    while(!vis[x]) vis[x]=1,vn[cn].pb(x),x=p[x];
  }
  
  for(int i=1;i<=m;i++) vis[i]=false;
  for(int i=1,x;i<=m;i++) if(!vis[i]){
    ++cm,x=i;
    while(!vis[x]) vis[x]=1,vm[cm].pb(x),x=q[x];
  } 
  
  for(int i=1;i<=n*m;i++) cin>>a[i];
  
  iota(fa,fa+cn+cm+1,0);
  ans=1,res=1;
    
  for(int i=1;i<=cn;i++) if((int)vn[i].size()==1){
    int h=vn[i][0];
    vector<int> lcm(0);
    for(int j=1;j<=cm;j++) if((int)vm[j].size()!=1){
      vector<int> V(0);
      for(auto k:vm[j]) V.pb(a[id(h,k)]);
      lcm.pb(calc(V));
    }
    ans=mul(ans,LCM(lcm));
  }
  
  for(int j=1;j<=cm;j++) if((int)vm[j].size()==1){
    int w=vm[j][0];
    vector<int> lcm(0);
    for(int i=1;i<=cn;i++) if((int)vn[i].size()!=1){
      vector<int> V(0);
      for(auto k:vn[i]) V.pb(a[id(k,w)]);
      lcm.pb(calc(V));
    }
    ans=mul(ans,LCM(lcm));
  }
  
  for(int i=1;i<=cn;i++) if((int)vn[i].size()!=1)
    for(int j=1;j<=cm;j++) if((int)vm[j].size()!=1){
      vector<int> V(0);
      for(auto h:vn[i]) for(auto w:vm[j]) V.pb(a[id(h,w)]),ct[a[id(h,w)]]=0;
      
      int cur=fac[(int)V.size()];
      bool fl=false;
      
      for(auto v:V){
        ++ct[v],cur=mul(cur,inv[ct[v]]);
        if(ct[v]>1) fl=1; 
      }
      
      if(!fl){
        cur=mul(cur,inv[2]);
        int u=((int)vn[i].size()&1)?0:cn+j,v=((int)vm[j].size()&1)?0:i;
        if(merge(u,v)) res=mul(res,2);
      }
      
      ans=mul(ans,cur);
    }
  
  cout<<mul(ans,res)<<'\n';
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int _;cin>>_;init();
  while(_--) SOLVE();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 31ms
memory: 75600kb

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: 15ms
memory: 74768kb

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: 283ms
memory: 81020kb

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:

wrong answer 44915th numbers differ - expected: '916890712', found: '383027013'