P4621 题解
dAniel_lele
·
·
题解
拆点，将每个位置拆成从上下左右四个方向进入的情况。
原图转化为一个内向基环树。
注意到一个细菌进入陷阱有且仅有四种情况，也就是从上下左右进入，且到达时间一定可以表示成 kx+b 或 b。
剩余都是 dirty work，具体可以见代码。
总复杂度 $O(4^k\times k^2\times(\log n+\log m)+\operatorname{poly}(nm))$。
```cpp
#include <bits/stdc++.h>
#define int __int128
#define add(i,j) ((i+j>=mod)?i+j-mod:i+j)
using namespace std;
int read(){
long long x; cin>>x;
return x;
}
void print(int x){
cout<<(long long)x;
}
int n,m,k;
struct node{
int mod,rem,mint;
};
struct pos{
int x,y;
char c;
friend bool operator <(pos a,pos b){
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
return a.c<b.c;
}
};
pos go(pos a){
if(a.c=='R'&&a.y==m) a.c='L';
if(a.c=='L'&&a.y==1) a.c='R';
if(a.c=='D'&&a.x==n) a.c='U';
if(a.c=='U'&&a.x==1) a.c='D';
if(a.c=='R') a.y++;
if(a.c=='L') a.y--;
if(a.c=='D') a.x++;
if(a.c=='U') a.x--;
return a;
}
pair<int,int> exgcd(int a,int b){
int tag=0;
if(a<b) swap(a,b),tag=1;
if(b==0){
return make_pair(1,0);
}
auto p=exgcd(b,a%b);
if(!tag) return make_pair(p.second,p.first-(a/b)*p.second);
return make_pair(p.first-(a/b)*p.second,p.second);
}
node excrt(node a,node b){
int d=__gcd(a.mod,b.mod);
if((a.rem-b.rem)%d!=0){
node ans; ans.mod=ans.rem=-1;
return ans;
}
auto p=exgcd(a.mod/d,b.mod/d);
// cout<<a.mod/d*p.first+b.mod/d*p.second<<"\n";
node ans; ans.mod=a.mod/__gcd(a.mod,b.mod)*b.mod;
ans.rem=(a.rem+(b.rem-a.rem)/d*p.first*a.mod)%ans.mod;
ans.mint=max(a.mint,b.mint);
while(ans.rem<0) ans.rem+=ans.mod;
// cout<<ans.rem%b.mod<<"\n";
return ans;
}
map<pos,int> mp;
node a[6][5];
int top[6];
map<char,int> num;
char val[4];
int g[55][55];
signed main(){
num['R']=0,num['D']=1,num['L']=2,num['U']=3;
val[0]='R',val[1]='D',val[2]='L',val[3]='U';
n=read(),m=read(),k=read();
int dx=read(),dy=read();
int x[k+1],y[k+1]; char c[k+1];
for(int i=1;i<=k;i++){
x[i]=read(),y[i]=read();
cin>>c[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char t; cin>>t;
g[i][j]=t-'0';
}
}
pos now; int cnt=0;
c[i]=val[(num[c[i]]+g[x[i]][y[i]])%4];
now.x=x[i],now.y=y[i],now.c=c[i];
mp.clear();
mp[now]=cnt; now=go(now),cnt++;
while(!mp[now]){
mp[now]=cnt;
// cout<<cnt<<" "<<now.x<<" "<<now.y<<" "<<now.c<<"\n";
cnt++;
now.c=val[(num[now.c]+g[now.x][now.y])%4];
now=go(now);
// cout<<now.x<<" "<<now.y<<"\n";
}
// cout<<cnt<<" "<<mp[now]<<" ";
int cyc=cnt-mp[now];
// cout<<cyc<<" ";
cnt=mp[now];
mp.clear();
while(!mp[now]){
mp[now]=cnt;
if(now.x==dx&&now.y==dy){
a[i][++top[i]].mint=cnt;
a[i][top[i]].mod=cyc;
a[i][top[i]].rem=cnt%cyc;
}
cnt++;
now.c=val[(num[now.c]+g[now.x][now.y])%4];
now=go(now);
}
cnt=0;
now.x=x[i],now.y=y[i],now.c=c[i];
while(!mp[now]){
mp[now]=cnt;
if(now.x==dx&&now.y==dy){
a[i][++top[i]].mint=cnt;
a[i][top[i]].mod=-1;
a[i][top[i]].rem=-1;
}
cnt++;
now.c=val[(num[now.c]+g[now.x][now.y])%4];
now=go(now);
}
if(top[i]==0){
cout<<"-1";
return 0;
}
// cout<<top[i]<<"\n";
// for(int j=1;j<=top[i];j++){
// cout<<a[i][j].mint<<" "<<a[i][j].mod<<" "<<a[i][j].rem<<"\n";
// }
}
int pw=1; for(int i=1;i<=k;i++) pw*=top[i];
int minv=1e18;
for(int j=0;j<pw;j++){
int cs[k+1],tmp=j;
for(int i=1;i<=k;i++){
cs[i]=tmp%top[i]+1;
tmp/=top[i];
}
node pre; pre.mint=0,pre.mod=1,pre.rem=0;
int eq=0;
for(int i=1;i<=k;i++){
if(a[i][cs[i]].mod==-1){
if(a[i][cs[i]].mint==eq||eq==0){
eq=a[i][cs[i]].mint;
}
else{
eq=-1;
break;
}
}
else{
pre=excrt(pre,a[i][cs[i]]);
if(pre.mod==-1){
eq=-1;
break;
}
}
}
if(eq==-1) continue;
while(pre.rem<pre.mint) pre.rem+=pre.mod;
if(eq==0||((eq-pre.rem>=0)&&((eq-pre.rem)%pre.mod==0))){
pre.rem=max(pre.rem,eq);
minv=min(minv,pre.rem);
}
}
if(minv>1e17){
cout<<-1;
}
else print(minv+1);
return 0;
}
```