結果

問題 No.590 Replacement
ユーザー vjudge1vjudge1
提出日時 2024-11-10 23:21:50
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 67 ms
9,296 KB
testcase_37 AC 70 ms
9,300 KB
testcase_38 AC 67 ms
9,168 KB
testcase_39 AC 67 ms
9,300 KB
testcase_40 AC 90 ms
8,448 KB
testcase_41 AC 89 ms
8,320 KB
testcase_42 AC 68 ms
9,232 KB
testcase_43 AC 75 ms
8,824 KB
testcase_44 AC 38 ms
9,088 KB
testcase_45 AC 71 ms
9,428 KB
testcase_46 AC 67 ms
9,304 KB
権限があれば一括ダウンロードができます

ソースコード

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