結果
問題 | No.590 Replacement |
ユーザー |
![]() |
提出日時 | 2020-04-13 15:56:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 2,292 bytes |
コンパイル時間 | 1,919 ms |
コンパイル使用メモリ | 147,200 KB |
最終ジャッジ日時 | 2025-01-09 18:04:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll MOD=1e9+7; ll inv(ll a, ll m){ ll b=m, x=1, y=0; while(b>0){ ll t=a/b; swap(a-=t*b, b); swap(x-=t*y, y); } return (x%m+m)%m; } int main() { int n; cin>>n; int a[100010], b[100010]; for(int i=0; i<n; i++){ cin>>a[i]; a[i]--; } for(int i=0; i<n; i++){ cin>>b[i]; b[i]--; } int p[100010], q[100010]; fill(p, p+n, -1); fill(q, q+n, -1); vector<int> va[100010], vb[100010]; int idx=0; for(int i=0; i<n; i++){ if(p[i]!=-1) continue; int x=i; do{ p[x]=idx; va[idx].push_back(x); x=a[x]; }while(x!=i); idx++; } idx=0; for(int i=0; i<n; i++){ if(q[i]!=-1) continue; int x=i; do{ q[x]=idx; vb[idx].push_back(x); x=b[x]; }while(x!=i); idx++; } int ra[100010], rb[100010]; for(int i=0; i<n; i++){ for(int j=0; j<va[i].size(); j++){ ra[va[i][j]]=j; } for(int j=0; j<vb[i].size(); j++){ rb[vb[i][j]]=j; } } map<P, vector<int>> mp; for(int i=0; i<n; i++){ mp[{p[i], q[i]}].push_back(i); } auto sum=[](ll m){ if(m%2==0) return m/2%MOD*((m-1)%MOD)%MOD; else return (m-1)/2%MOD*(m%MOD)%MOD; }; ll ans=0; for(auto pr:mp){ auto v=pr.second; int p1=pr.first.first, q1=pr.first.second; ll cp=va[p1].size(), cq=vb[q1].size(); ll g=gcd(cp, cq); map<ll, vector<ll>> mp1; for(auto i:v){ ll rp=ra[i], rq=rb[i]; ll s=(rq-rp%g+g)%g; rq=(rq-s+cq)%cq; ll x=inv(cp/g, cq/g)*(((rq-rp)/g)%(cq/g)+cq/g)%(cq/g); mp1[s].push_back(x*cp+rp); } for(auto pr2:mp1){ auto w=pr2.second; sort(w.begin(), w.end()); w.push_back(w[0]+cp*cq/g); for(int i=0; i<w.size()-1; i++){ ll m=w[i+1]-w[i]; //cout<<m<<" "<<sum(m)<<endl; (ans+=sum(m))%=MOD; } } } cout<<ans<<endl; return 0; }