Floyd的简单应用

Description

给出一张$n$点$m$边的无向图，有一个机器人，起点在$1$号点上，机器人会进行$t$次操作。

一次操作可能包括：移动到与现在点直接相连的点上，停留在现在的点上，自爆（自爆之后不能进行操作）

求机器人行为的方案数，对$2017$取模。

$t \leq 10^9, n,m \leq 100$.

Samples

Input #1

Output #1

Solution

考虑建出这张图的邻接矩阵$\rm G$.

从$\rm Floyd$算法的角度来分析, 容易发现${\rm G}^k_{i,j}$表示的是从$\rm i$点到$\rm j$点走$k$步的方案数.

对于停在原地这个操作, 我们对每个城市连一条自环即可.

对于自爆, 我们建出一个虚点表示这个状态, 然后从每个点向它连一条有向边.

然后矩阵快速幂算出${\rm G}^k$, 统计$\sum_{i=0}^n {\rm G}_{1, i}$即可.

Code

/* Headers */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <stack>
#include <map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define RevEdge(x) x^1
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE], *is = ibuf, *its = ibuf;
    char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
    inline char getch() {
        if(is == its)
            its = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
        return (is == its) ? EOF : *is++;
    }
    inline int getint() {
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-') {neg = 1;ch = getch();}
        while(isdigit(ch)) {
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg ? -res : res;
    }
    inline void flush(){
        fwrite(obuf, 1, os - obuf, stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot) flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--) putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x, bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 3e1 + 10, mod = 2017;
int n, m, k, ans;
struct Matrix {
    int n, m, ary[MAXN][MAXN];
    inline Matrix() {}
    inline Matrix(int n, int m) : n(n), m(m) {memset(ary, 0, sizeof ary);}
    inline friend Matrix operator * (Matrix A, Matrix B) {
        Matrix res(A.n, B.m);
        FOR(i, 0, res.n, 1) FOR(k, 0, A.m, 1) FOR(j, 0, res.m, 1)
            (res.ary[i][j] += A.ary[i][k] * B.ary[k][j]) %= mod;
        return res;
    }
};
/* functions */
inline Matrix quick_MatPower(Matrix &base, int b) {
    Matrix res(30, 30);
    FOR(i, 0, 30, 1) res.ary[i][i] = 1;
    while(b) {
        if(b & 1) res = res * base;
        b >>= 1; base = base * base;
    } return res;
}
int main(int argc, char *argv[]) {
    //FILE_IN("data.in");
    read(n); read(m); Matrix Graph(n, n);
    FOR(i, 1, m, 1) {
        int u, v; read(u); read(v);
        Graph.ary[u][v] = Graph.ary[v][u] = 1;
    } FOR(i, 0, n, 1) Graph.ary[i][i] = 1;
    FOR(i, 1, n, 1) Graph.ary[i][0] = 1; // The Robot explodes itself.
    read(k); Matrix End(n, n); End = quick_MatPower(Graph, k);
    FOR(i, 0, n, 1) (ans += End.ary[1][i]) %= mod;
    printf("%d\n", ans);
    return 0;
}

~~感觉这篇post有点水了~~

LuoguP3758/P5789「TJOI2017」题解