結果

問題 No.590 Replacement
ユーザー lam6er
提出日時 2025-03-26 16:02:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 105 ms / 2,000 ms
コード長 2,046 bytes
コンパイル時間 3,416 ms
コンパイル使用メモリ 202,936 KB
実行使用メモリ 10,892 KB
最終ジャッジ日時 2025-03-26 16:02:34
合計ジャッジ時間 6,163 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 47
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:51:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:52:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |         for(int i=1;i<=n;++i)scanf("%d",&a[i]),p[a[i]]=i;
      |                              ~~~~~^~~~~~~~~~~~
main.cpp:53:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |         for(int i=1;i<=n;++i)scanf("%d",&b[i]),q[b[i]]=i;
      |                              ~~~~~^~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int a[100005],b[100005];
int p[100005],q[100005];
int vist[100005];
int dp[100005],wp[100005],rp[100005];
int dq[100005],wq[100005],rq[100005];
pair<long long,int>pi[100005];
long long bs[100005];
void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-a/b*y;
}
int niyuan(int a,int b){
    int x=0,y=0;exgcd(a,b,x,y);
    return (x%b+b)%b;
}
long long crt(int r1,int m1,int r2,int m2,int g){
    int gg=r1%g;
    r1/=g,m1/=g,r2/=g,m2/=g;
    long long an=0;
    an=(1ll*r1*m2*niyuan(m2,m1)+1ll*r2*m1*niyuan(m1,m2))%(1ll*m1*m2);
    return an*g+gg;
}
int suan(vector<int>v){
    long long N=0;
    int t=0;
    for(auto x:v){
        int g=__gcd(dp[x],dq[x]);
        N=1ll*dp[x]*dq[x]/g;
        int qm=((wq[x]-wp[x])%g+g)%g;
        wq[x]=(wq[x]-qm+dq[x])%dq[x];
        bs[++t]=crt(wp[x],dp[x],wq[x],dq[x],g);
    }
    sort(bs+1,bs+t+1);
    bs[t+1]=bs[1]+N;
    int ans=0;
    for(int i=1;i<=t;++i){
        int y=(bs[i+1]-bs[i])%mod;
        ans=(ans+1ll*y*(y-1)/2)%mod;
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),p[a[i]]=i;
    for(int i=1;i<=n;++i)scanf("%d",&b[i]),q[b[i]]=i;
    for(int i=1;i<=n;++i)if(!vist[i]){
        int x=i;
        vector<int>v;
        while(1){
            v.emplace_back(x);
            vist[x]=1;x=p[x];
            if(x==i)break;
        }
        int k=v.size();
        for(int j=0;j<k;++j)dp[v[j]]=k,wp[v[j]]=j,rp[v[j]]=i;
    }
    memset(vist,0,sizeof(vist));
    for(int i=1;i<=n;++i)if(!vist[i]){
        int x=i;
        vector<int>v;
        while(1){
            v.emplace_back(x);
            vist[x]=1;x=q[x];
            if(x==i)break;
        }
        int k=v.size();
        for(int j=0;j<k;++j)dq[v[j]]=k,wq[v[j]]=j,rq[v[j]]=i;
    }
    for(int i=1;i<=n;++i){
        int A=(wp[i]-wq[i]+dq[i])%__gcd(dp[i],dq[i]);
        int B=rp[i],C=rq[i];
        long long hx=1ll*A*(n+1)*(n+1)+1ll*B*(n+1)+C;
        pi[i]=make_pair(hx,i);
    }
    sort(pi+1,pi+n+1);
    int ans=0;
    for(int i=1;i<=n;){
        int j=i;
        while(j<=n&&pi[j].first==pi[i].first)++j;
        vector<int>g;
        for(int k=i;k<j;++k)g.emplace_back(pi[k].second);
        ans=(ans+suan(g))%mod;
        i=j;
    }
    printf("%d\n",ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0