题解 CF995E 【Number Clicker】
swiftc
2019-08-18 20:07:05
~~这道题我一开始看还以为是数学题~~
求逆元其实就可以看完随机跳到另一个位置，那么根据生日悖论，状态数不会太多，双向bfs即可
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int u,v,p;
map<int,int>vis1,vis2,nxt,pre;//记录每一个位置有么有被访问过和是哪跳过来的
queue<int> q1,q2;
int qpow(int a,int b){
if(b==0)return 1;
int tmp=qpow(a,b/2);
return b%2?tmp*tmp%p*a%p:tmp*tmp%p;
}
main(){
scanf("%lld%lld%lld",&u,&v,&p);
q1.push(u);
q2.push(v);
vis1[u]=1;
pre[u]=-1;
vis2[v]=1;
nxt[v]=-1;
while(!q1.empty()){
int now=q1.front();
q1.pop();
if(vis2[now]){
printf("%lld\n",vis1[now]+vis2[now]-2);
stack<int>s;
int tmp=now;
while(tmp!=-1){
s.push(tmp);
tmp=pre[tmp];
}
while(s.size()!=1){
int k=s.top();
s.pop();
if((k+1)%p==s.top()){
printf("1 ");
}
else if((k+p-1)%p==s.top()){
printf("2 ");
}
else{
printf("3 ");
}
}
tmp=now;
while(nxt[tmp]!=-1){
if((tmp+1)%p==nxt[tmp]){
printf("1 ");
}
else if((tmp+p-1)%p==nxt[tmp]){
printf("2 ");
}
else{
printf("3 ");
}
tmp=nxt[tmp];
}
return 0;
}
if(!vis1[(now+1)%p])q1.push((now+1)%p),vis1[(now+1)%p]=vis1[now]+1,pre[(now+1)%p]=now;
if(!vis1[(now-1+p)%p])q1.push((now-1+p)%p),vis1[(now-1+p)%p]=vis1[now]+1,pre[(now-1+p)%p]=now;
int power=qpow(now,p-2);
if(!vis1[power])q1.push(power),vis1[power]=vis1[now]+1,pre[power]=now;
now=q2.front();q2.pop();
if(!vis2[(now+1)%p])q2.push((now+1)%p),vis2[(now+1)%p]=vis2[now]+1,nxt[(now+1)%p]=now;
if(!vis2[(now-1+p)%p])q2.push((now-1+p)%p),vis2[(now-1+p)%p]=vis2[now]+1,nxt[(now-1+p)%p]=now;
power=qpow(now,p-2);
if(!vis2[power])q2.push(power),vis2[power]=vis2[now]+1,nxt[power]=now;
}
}
```
还有...
据我们学校的学长说，双向广搜可能搜出来的不是最优解