退役稳如狗，文化学不走

题目大意

给定一个 $n$ 个点的有向图，问从任意一点出发最后回到该点的长度小于 $k$ 的路径数 模 $m$

数据范围

30 —- $n <= 40, k <= 1000$

100 —- $n <= 100, k <= 1e6, m <= 1e9$

题解

首先，如果你像我一样脑残，那么你很容易就能想到30分的做法

DFS

滚吧。天知道会在图里面转多久才出来。

矩阵乘法

很明显大家都知道邻接矩阵可以用来统计路径数， 令邻接矩阵为 $G$

很明显答案为 $ans = G + G ^ 2 + G ^ 3 + … + G^{k-1}$

对于每一步每次 $n^3$ 乘起来然后统计答案， $O(n^3k)$ ，30分稳了

AC是不可能的，这辈子都不可能的，正解又不会写，就是骗骗分，才维持了现在这样子

考虑优化，$O(N^3)$ 是不可能变的，这辈子都不可能…咳

我们定义一个矩阵集合为 $T$ ,其中 $T_0 = G, T_i = T_{i-1} \times T_{i-1} (i = 2,3,4…)$

对于我们进行的 $k-1$ 步乘法，我们可以发现

$G + G^2 + G^3 + G^4 = (G^1 + G^2) \times T_1 + (G^1 + G^2)$

这时候我们灵机一动，是不是说我们可以拆成$logk$ 个矩阵来做

于是就有了结果

定义矩阵 $pre, ans, T, sum$

$pre$ 表示 $G^{now-1}$, $sum$ 表示统计的答案， $ans_i$ 表示 $G^0$ 到 $G^{2^i}$ 长度的矩阵的和

这时我们对 $k$ 进行二进制处理，如果当前位 $(now)$ 为 1

最后取 $sum$ 对角线上的元素之和即可，时间复杂度 $O(n^3logk)$ ,卡卡常就过了

代码

/*"Nothing is true."*/
#include<bits/stdc++.h>
using namespace std;
inline int min(int _a, int _b) {return _a < _b ? _a : _b;}
inline int max(int _a, int _b) {return _a > _b ? _a : _b;}
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
typedef long long ll;
template <class _T> inline void rd(_T &_a) {
	int _f=0,_ch=getchar();_a=0;
	while(_ch<'0' || _ch>'9') {if(_ch == '-')_f = 1; _ch = getchar();}
	while(_ch > ='0' && _ch<='9')_a= (_a<<1)+(_a<< 3)+_ch-'0',_ch=getchar();
	if(_f) _a=-_a;
}

struct con {
	long long m[101][101];
} mp, ans[30], T[30], pre, sum;

long long n, M, K;

con cheng(con A, con B) {
	con C; memset(C.m, 0, sizeof C.m);
	for(int i = 0;i < n; ++i) {
		for(int j = 0;j < n; ++j) {
			for(int k = 0;k < n; ++k) {
				C.m[i][j] += (A.m[i][k] * B.m[k][j]) % M;
				if(C.m[i][j] >= M) C.m[i][j] -= M;
			}
		}
	}
	return C;
}

con jia(con A, con B) {
	con C; memset(C.m, 0, sizeof C.m);
	for(int i = 0;i < n; ++i) {
		for(int j = 0;j < n; ++j) {
			C.m[i][j] = A.m[i][j] + B.m[i][j];
			if(C.m[i][j] >= M) C.m[i][j] -= M;
		}
	}
	return C;
}

char s[110];

int main() {
	//freopen("tour.in","r",stdin);
	//freopen("tour.out","w",stdout);
	rd(n);
	for(int i = 0;i < n; ++i) {
		scanf("%s", s);
		for(int j = 0;j < n; ++j) {
			if(s[j] == 'Y') mp.m[i][j] = 1;
		}
	}
	rd(K); rd(M); --K;
	ans[0] = mp; luo[0] = mp;
	long long res = 0;
	long long x = 1;
	while(K >= (1 << x)) {
		ans[x] = cheng(ans[x - 1], T[x - 1]);
		T[x] = cheng(T[x - 1], T[x - 1]);
		ans[x] = jia(ans[x], ans[x - 1]);
		++x;
	}
	int ct = 0;

	for(int i = 0;i < n; ++i) pre.m[i][i] = 1;

	while(K) {
		if(K & 1) {
			sum = jia(sum, cheng(pre, ans[ct]));
			pre = cheng(pre, T[ct]);
		}
		K >>= 1; ++ct;
	}
	for(int i = 0;i < n; ++i) {
		res += sum.m[i][i];
		if(res >= M) res -= M;
	}
	printf("%lld\n", res);
	return 0;
}