题解 CF995E 【Number Clicker】

swiftc · 2019-08-18 20:07:05 · 题解

这道题我一开始看还以为是数学题

求逆元其实就可以看完随机跳到另一个位置，那么根据生日悖论，状态数不会太多，双向bfs即可

#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;
    }
}

还有...

据我们学校的学长说，双向广搜可能搜出来的不是最优解