Poweroj - 2912 先知归来

传送门：Poweroj - 2912

思路分析

把图转化为矩阵，没做一次转移，相当于做了一次矩阵乘法，普通的矩阵快速幂会超时，因为是01矩阵，用bitset优化矩阵

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
 
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
 
const int INF = 0x3f3f3f3f;
const int N = 515;

struct Mat {
    int n;
    bitset<N>r[N];
    bitset<N>c[N];
    Mat(int nn) {
        n = nn;
        for(int i=1; i<=n; i++) r[i].reset(),c[i].reset();
    }
 
    Mat operator* (const Mat B) const {
        Mat res(n);
        for(int i=1; i<=n; i++) {
            if(r[i].count() == 0) continue;
            for(int j = 1; j<=n; j++) {
                int f = (r[i]&B.c[j]).any();
                res.r[i][j] = f;
                res.c[j][i] = f;
            }
        }
        return res;
    }
     
    Mat pow(__int128 x){
        Mat res(n),bas(n);
        for(int i=1;i<=n;i++) res.r[i][i] = 1,res.c[i][i] = 1;
        for(int i=1;i<=n;i++) bas.r[i] = r[i],bas.c[i] = c[i];
        while(x){
            if(x&1) res = res*bas;
            x>>=1;
            bas = bas*bas;
        }
        for(int i=1;i<=n;i++) r[i] = res.r[i],c[i] = res.c[i];
        return res;
    }
};
 
int main() {
 
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
 
    int n,s,t;
    __int128 o;
    read(n,s,t,o);
    Mat ans(n);
    int m;
    read(m);
    while(m--) {
        int u,v;
        read(u,v);
        ans.r[u][v] = 1;
        ans.c[v][u] = 1;
    }
    ans.pow(o);
    if(ans.r[s][t] == 1) puts("They call me Prophet");
    else puts("Remember me");
 
 
 
 
 
    return 0;
}