bzoj_3583 杰杰的女性朋友

题目:

  杰杰是魔法界的一名传奇人物。他对魔法具有深刻的洞察力,惊人的领悟力,以及令人叹为观止的创造力。自从他从事魔法竞赛以来,短短几年时间,就已经成为世界公认的实力最强的魔法选手之一。更让人惊叹的是,他几乎没有借助外界力量,完全凭借自己的努力达到了普通人难以企及的高度。在最近的世界魔法奥林匹克竞赛上,他使用高超的魔法本领,一路过关斩将,在最后时刻一举击败了前冠军“旅行者”,获得了魔法界最高的荣耀:女神奖杯!女神奖杯可不是一个普通的奖杯,她能够帮杰杰实现一个愿望。
  杰杰本着实事求是的态度,审时度势,向女神奖杯提出了自己的愿望:想要一个女性朋友。
  杰杰的愿望实现了,可是女性朋友却和他不在一个城市。杰杰想要知道:如果要到达女性朋友的所在城市,有多少种方案供他选择?
  杰杰所在的世界有n个城市,从1到n进行编号。任意两个城市都通过有向道路连接。每个城市u有k个入点权:,有k个出点权:。对于任意两个城市(u,v)(u可以等于v),u到v的道路条数为()条。杰杰有m次询问,每次询问由三元组(u,v,d)构成,询问从u城市通过不超过d条道路到达v城市的方案数。
  为了温柔的杰杰和他的女性朋友的美好未来,帮助他解答这个问题吧。

思路:

  先根据 数组预处理出每两点之间的边数 ,那么从 步的方案数就是 。不难发现这个是可以用矩阵进行转移的,这样就有了一个 优秀做法。
  注意到 ,也就是说 。那最后的矩阵就可以写成 。因为 得到的是一个 的矩阵,所以这里的复杂度就只有 。然后因为要求的其实只有矩阵中某一点的值,所以可以先 的算出 ,然后再 算出某一点的值。
  因为题目要求不超过 步的方案数,所以只要再把 连到一个新点上,新点连一个自环,然后走 步在新点上绕圈圈即可。
  ps:题目卡我结构体写的矩阵,只好拆开写成全局数组了qwq。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int MOD = 1000000007, N = 1005, K = 25;

void read(int &x) {
    char c;
    for(c = getchar(); !isdigit(c); c = getchar());
    for(x = 0; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + c - '0';
}

inline void add(int &a, int b) {
    if((a += b) >= MOD) a -= MOD;
}

void calc(int A[N][N], int B[N][N], int C[N][N], int n, int k, int m) {
    static int T[N][N];
    rep(i, 1, n) rep(j, 1, m) {
        T[i][j] = 0;
        rep(x, 1, k) add(T[i][j], (ll) A[i][x] * B[x][j] % MOD);
    }
    rep(i, 1, n) rep(j, 1, m) C[i][j] = T[i][j];
}

void qkpow(int x[N][N], int t[N][N], int n, int k) {
    static int ans[N][N];
    rep(i, 1, n) rep(j, 1, n) ans[i][j] = (i == j);
    for(; k; k >>= 1, calc(x, x, x, n, n, n))
        if(k & 1) calc(ans, x, ans, n, n, n);
    rep(i, 1, n) rep(j, 1, n) t[i][j] = ans[i][j];
}

int n, k, in[N][N], out[N][N], tmp[N][N];
int qry(int u, int v, int d) {
    if(d == 0) return u == v;
    out[v][k + 1] = out[n + 1][k + 1] = in[k + 1][n + 1] = 1;
    calc(in, out, tmp, k + 1, n + 1, k + 1);
    qkpow(tmp, tmp, k + 1, d);
    calc(out, tmp, tmp, n + 1, k + 1, k + 1);
    int ans = 0;
    rep(i, 1, k + 1) add(ans, (ll) tmp[u][i] * in[i][n + 1] % MOD);
    out[v][k + 1] = out[n + 1][k + 1] = in[k + 1][n + 1] = 0;
    return ans;
}

int main() {
    int m, u, v, d;
    read(n); read(k);
    rep(i, 1, n) {
        rep(j, 1, k) read(out[i][j]);
        rep(j, 1, k) read(in[j][i]);
    }
    read(m);
    while(m--) {
        read(u); read(v); read(d);
        printf("%d\n", qry(u, v, d));
    }
    return 0;
}