結果
問題 | No.590 Replacement |
ユーザー |
![]() |
提出日時 | 2017-04-15 15:12:12 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,649 bytes |
コンパイル時間 | 1,248 ms |
コンパイル使用メモリ | 87,840 KB |
実行使用メモリ | 17,184 KB |
最終ジャッジ日時 | 2024-07-19 09:28:27 |
合計ジャッジ時間 | 5,299 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <algorithm>using namespace std;typedef long long ll;typedef vector<int> vi;typedef vector<ll> vl;typedef pair<int,int> P;typedef vector<P> vp;const ll mod=1e9+7;ll gcd(ll a,ll b){if(!b) return a;return gcd(b,a%b);}ll lcm(ll a,ll b){return a/gcd(a,b)*b;}ll Pow_mod(ll n,ll p){ll r=1;for(;p>0;p>>=1){if(p&1) r=(r*n)%mod;n=(n*n)%mod;}return r;}ll Division_mod(ll n,ll m){return n*Pow_mod(m,mod-2)%mod;}int n;vi a,b;vi ac,ad,as,bc,bd,bs;map<pair<P,int>,vp> m;void f(vi& A,vi& C,vi& D,vi& S){for(int i=0;i<n;i++){cin>>A[i];A[i]--;}int cnt=0;for(int i=0;i<n;i++) if(C[i]==-1){int I=i,num=0;do{C[I]=cnt;D[I]=num;num++;I=A[I];}while(I!=i);S.push_back(num);cnt++;}}int main(){ios::sync_with_stdio(0);cin>>n;a=b=ad=bd=vi(n);ac=bc=vi(n,-1);f(a,ac,ad,as);f(b,bc,bd,bs);for(int i=0;i<n;i++){int g=gcd(as[ac[i]],bs[bc[i]]);m[{{ac[i],bc[i]},(ad[i]%g-bd[i]%g+g)%g}].push_back({ad[i],bd[i]});}ll res=0;for(auto i=m.begin();i!=m.end();i++){P tmp=i->first.first;vp v=i->second;int A=as[tmp.first],B=bs[tmp.second],S=v.size();ll l=lcm(A,B),g=gcd(A,B),P=v[0].first,Q=v[0].second;vl u(S+1),w(B/g);u[S]=l;int I=Q/g;for(int i=0;i<B/g;i++){(I+=A/g)%=B/g;w[I]=B/g-i-1;}for(int i=1;i<S;i++){ll X=v[i].first,Y=v[i].second,num;num=(P+A-X)%A;(Y+=num)%=B;num+=w[Y/g]*A;u[i]=num;}sort(u.begin(),u.end());for(int i=0;i<S;i++){ll sa=(u[i+1]-u[i])%mod;(res+=Division_mod(sa*(sa-1)%mod,2))%=mod;}}cout<<res<<endl;}