これは考え方は難しくないな…。
https://codeforces.com/contest/1515/problem/G
問題
有向グラフが与えられる。各辺には長さがある。
以下のクエリに順次答えよ。
頂点vと、正整数S,Tが指定される。
vから辺をたどってまた元の頂点に戻るとき、移動量をTで割った余りがT-Sとなる経路があるか判定せよ。
解法
まずグラフを強連結成分分解しよう。
連結成分内は任意に移動できることを考えると、連結成分内をDFSし、閉路のGCDを取ろう。
その場合、この連結成分内ではこのGCDの分だけ移動量を増やすことができる。
次に各クエリについて答える。
CRTを使い、先ほど求めたGCDの値とS,Tを用いて、条件を満たす移動経路の有無を判定しよう。
int N,M; ll D[303030]; ll G[303030]; int vis[303030]; vector<pair<int,int>> E[202020]; class SCC { public: static const int MV = 2025000; vector<vector<int> > SC; int NV,GR[MV]; private: vector<int> E[MV], RE[MV], NUM; int vis[MV]; public: void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}} void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); } void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); } void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);} void scc() { int c=0,i; SC.clear(); SC.resize(NV); NUM.clear(); assert(NV); FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0; for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){ SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++; } SC.resize(c); } }; SCC scc; __int128 ext_gcd(__int128 p,__int128 q,__int128& x, __int128& y) { // get px+qy=gcd(p,q) if(q==0) return x=1,y=0,p; __int128 g=ext_gcd(q,p%q,y,x); y-=p/q*x; return g; } pair<__int128,__int128> crt(__int128 a1,__int128 mo1,__int128 a2,__int128 mo2) { // return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2 __int128 g,x,y,z; g=ext_gcd(mo1,mo2,x,y); a1=(a1%mo1+mo1)%mo1;a2=(a2%mo2+mo2)%mo2; if(a1%g != a2%g) return pair<__int128,__int128>(-1,0); // N/A __int128_t lcm=mo1*(mo2/g); if(lcm<mo1) return pair<__int128,__int128>(-2,0); // overflow __int128_t v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g); return make_pair(((v%lcm)+lcm) % lcm,lcm); } void dfs(int cur,ll sum) { if(D[cur]>=0) { G[scc.GR[cur]]=__gcd(G[scc.GR[cur]],abs(sum-D[cur])); return; } D[cur]=sum; FORR2(e,c,E[cur]) if(scc.GR[cur]==scc.GR[e]) dfs(e,sum+c); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; scc.init(N); FOR(i,M) { cin>>x>>y>>k; x--,y--; scc.add_edge(y,x); E[y].push_back({x,k}); } scc.scc(); MINUS(D); FOR(i,N) if(D[i]<0) dfs(i,0); int Q; cin>>Q; while(Q--) { int cur; ll S,T; cin>>cur>>S>>T; cur--; S=(T-S)%T; ll TG=G[scc.GR[cur]]; if(S==0) { cout<<"YES"<<endl; } else { if(TG==0) { cout<<"NO"<<endl; } else { auto p=crt(0,TG,S,T); if(p.first>0) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } } }
まとめ
個々のステップの考え方はそこまで難しくないんだよな。