結果

問題 No.590 Replacement
ユーザー vjudge1vjudge1
提出日時 2024-11-10 12:38:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 2,046 bytes
コンパイル時間 2,494 ms
コンパイル使用メモリ 176,952 KB
実行使用メモリ 10,904 KB
最終ジャッジ日時 2024-11-10 12:38:30
合計ジャッジ時間 5,659 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 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 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 6 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 7 ms
5,248 KB
testcase_10 AC 4 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 7 ms
5,248 KB
testcase_13 AC 28 ms
6,144 KB
testcase_14 AC 45 ms
7,040 KB
testcase_15 AC 5 ms
5,248 KB
testcase_16 AC 11 ms
5,248 KB
testcase_17 AC 18 ms
5,504 KB
testcase_18 AC 62 ms
9,436 KB
testcase_19 AC 67 ms
8,780 KB
testcase_20 AC 16 ms
5,248 KB
testcase_21 AC 84 ms
9,772 KB
testcase_22 AC 74 ms
10,396 KB
testcase_23 AC 83 ms
10,428 KB
testcase_24 AC 92 ms
9,944 KB
testcase_25 AC 90 ms
9,880 KB
testcase_26 AC 92 ms
10,008 KB
testcase_27 AC 88 ms
10,392 KB
testcase_28 AC 87 ms
9,884 KB
testcase_29 AC 90 ms
9,624 KB
testcase_30 AC 96 ms
9,724 KB
testcase_31 AC 94 ms
10,240 KB
testcase_32 AC 91 ms
10,268 KB
testcase_33 AC 3 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 46 ms
10,884 KB
testcase_37 AC 48 ms
10,860 KB
testcase_38 AC 45 ms
10,776 KB
testcase_39 AC 44 ms
10,904 KB
testcase_40 AC 50 ms
9,624 KB
testcase_41 AC 51 ms
9,736 KB
testcase_42 AC 50 ms
10,504 KB
testcase_43 AC 50 ms
10,136 KB
testcase_44 AC 44 ms
9,472 KB
testcase_45 AC 49 ms
10,904 KB
testcase_46 AC 49 ms
10,892 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0