結果

問題 No.590 Replacement
ユーザー vjudge1vjudge1
提出日時 2024-11-10 23:21:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,396 bytes
コンパイル時間 2,186 ms
コンパイル使用メモリ 175,372 KB
実行使用メモリ 9,428 KB
最終ジャッジ日時 2024-11-10 23:21:57
合計ジャッジ時間 5,733 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define LL long long
#define MOD 1000000007
int ans,N,a[300009],i1[300009],n1[300009],c1[300009],s1[300009],
b[300009],SZ1,SZ2,le,i2[300009],n2[300009],c2[300009],s2[300009];
struct n_t{
    int h1,p1,h2,p2;
} t[300009];
bool cmp(n_t x,n_t y) {
    if(x.h1!=y.h1) return x.h1<y.h1;
    return x.h2<y.h2;
}
bool cmp2(n_t x,n_t y) {
    int a=(x.p2%le-x.p1%le+le)%le;
    int b=(y.p2%le-y.p1%le+le)%le;
    return a<b;
}
void add(LL x) {
    x%=MOD;
    ans=(ans+1ll*x*(x-1)/2)%MOD;
}
void exgcd(int a,int b,int& c,int& d) {
    if(b==0) {
        c=1;d=0;
        return;
    }
    exgcd(b,a%b,d,c);
    d-=(a/b)*c;
}
int iv(int a,int b) {
    int c,d;
    exgcd(a,b,c,d);
    c=(c%b+b)%b;
    return c;
}
LL qr(int x,int y) {
    y=(y-x+SZ2)%SZ2;
    int as=iv(SZ1/le,SZ2/le);
    LL ct=(x+1ll*y*as*SZ1)%(1ll*SZ1*SZ2/le);
    return ct;
}
void sv2(int l,int r) {
    std::vector<LL> tp;
    tp.push_back(0);
    tp.push_back(1ll*SZ1*SZ2/le);
    for(int i=l+1;i<=r;i++) {
        tp.push_back(qr((t[i].p1-t[l].p1+SZ1)%SZ1,(t[i].p2-t[l].p2+SZ2)%SZ2));
    }
    std::sort(tp.begin(),tp.end());
    for(int i=0;i+1<tp.size();i++) {
        add(tp[i+1]-tp[i]);
    }
}
void sv(int l,int r) {
    SZ1=s1[t[l].h1];
    SZ2=s2[t[l].h2];
    le=std::__gcd(s1[t[l].h1],s2[t[l].h2]);
    std::sort(t+l,t+r+1,cmp2);
    int lx=l;
    for(int i=l+1;i<=r;i++) {
        if(cmp2(t[i-1],t[i])) {
            sv2(lx,i-1);
            lx=i;
        }
    }
    sv2(lx,r);
}
signed main(void) {
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d",&a[i]);
        i1[a[i]]=i;
    }
    for(int i=1;i<=N;i++) {
        if(c1[i]) continue;
        int x=i;
        do{
            n1[x]=s1[i];
            c1[x]=i;
            s1[i]++;
            x=a[x];
        }while(x!=i);
    }
    for(int i=1;i<=N;i++) {
        scanf("%d",&b[i]);
        i2[b[i]]=i;
    }
    for(int i=1;i<=N;i++) {
        if(c2[i]) continue;
        int x=i;
        do{
            n2[x]=s2[i];
            c2[x]=i;
            s2[i]++;
            x=b[x];
        }while(x!=i);
    }
    for(int i=1;i<=N;i++) {
        t[i]=(n_t){c1[i1[i]],n1[i1[i]],c2[i2[i]],n2[i2[i]]};
    }
    std::sort(t+1,t+N+1,cmp);
    int l=1;
    for(int i=2;i<=N;i++) {
        if(t[i-1].h1!=t[i].h1||t[i-1].h2!=t[i].h2) {
            sv(l,i-1);
            l=i;
        }
    }
    sv(l,N);
    printf("%d",ans);
}
0