image.png

#include <bits/stdc++.h>
#define ll long long
#define P 2009
using namespace std;
const int N=100;
int n,m,k,s,t;
struct Matrix{
	ll a[N][N];
	Matrix(){ memset(a,0,sizeof(a));}//构造函数，矩阵初始化全零 
	Matrix operator*(Matrix &b)const{//重载乘法运算 
		Matrix tmp;
		for (int k=0;k<=m;++k)
			for (int i=0;i<=m;++i)
				for (int j=0;j<=m;++j)
					(tmp.a[i][j]+=a[i][k]*b.a[k][j])%=P;
		return tmp;
	}
}a,ans;
void qpow(ll p){
	for (int i=0;i<=m;++i)
		ans.a[i][i]=1;//ans初始化为单位矩阵 
	while (p){
		if (p&1) ans=ans*a;
		a=a*a;
		p>>=1;
	}
}
int main(){
	freopen("in.txt","r",stdin);
	cin>>n>>t;m=(n-1)*9+8;
	char c;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j){
			cin>>c;
			k=c-'0';
			if (k) a.a[(i-1)*9][(j-1)*9+k-1]=1;//i号点向距离j号点k-1距离的点连边 
		}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=8;++j) a.a[(i-1)*9+j][(i-1)*9+j-1]=1;//每轮减少1的距离 
	qpow(t);
	cout<<ans.a[0][(n-1)*9];
} 

狗头上几个！ 对于 100 % 100%100% 的数据解法 这100分很难拿，我做的时候调了一周呢。

我们看到这t的数据范围时，就应该条件反射的想到时间复杂度应该是有个 log ⁡ t \log tlogt 的，事实的确如此。

有人还是有点懵啊，怎么弄呢？

这时候我们先来思考下一个前置问题：

我们把每一条路的长度都改成1或0，其他都不变。 1 是不是感觉到了什么。 其实上面这个问题就是个矩阵快速幂吗。（不知道啥是“矩阵快速幂”的，尽请期待我的下一篇blog：矩阵快速幂）

所以如果要解决上面这个问题的话我们会发现其实他的答案就是 G t G^t G t

这里G为邻接矩阵。

怎么把问题转换成刚才哪一种呢？ 其实我们并不需要更改快速幂那一部分，只要改建图方式就行了（因为 n nn 很友好）

怎么建图呢？

我们可以这样建：就是比如有以下关系

2 4 1 1 2 3 4 我们可以把它变成这样：

1 a b c 2 3 4 这样虽然点数要多8倍，但起码比搜索好太多了，我们只需要给每个点都安排8个后继节点，然后每一个都像这样连（就像连面包板一样）

那我们最后的时间复杂度便是矩阵乘法的复杂度乘上快速幂的那个 log ⁡ \loglog

即整体复杂度： Θ ( ( 10 n ) 3 log ⁡ t ) \Theta((10n)^3\log t)Θ((10n) 3 logt)

卡卡就能过，但是很容易卡常，千万小心，因为出题人很毒瘤。

愉快地贴上代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100 + 20;
const int mod = 2009;
typedef long long ll;

char s[15][15];
int G[maxn][maxn];
struct Matrix {
int n, m;
int a[maxn][maxn];
Matrix() { memset(a, 0, sizeof a); }
Matrix(int _n, int _m) {
n = _n;
m = _m;
memset(a, 0, sizeof a);
}
};

Matrix mul(Matrix &a, Matrix &b) {
Matrix res(a.n, b.m);
for (int i = 0; i < a.n; i++)
for (int j = 0; j < b.m; j++)
for (int k = 0; k < a.m; k++) {
res.a[i][j] += a.a[i][k] * b.a[k][j];
res.a[i][j] %= mod;
}
return res;
}

Matrix Pow(Matrix &base, int n) {
Matrix res(base.n, base.n);
for (int i = 0; i < base.n; i++) res.a[i][i] = 1;
while (n) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res;
}

int main() {
// freopen("lost.in", "r", stdin);
// freopen("lost.out", "w", stdout);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%s", s[i]);
Matrix G(10 * n - 1, 10 * n - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int now = s[i][j] - '0';
if (now == 0) continue;
G.a[10 * i + now - 1][10 * j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 8; j++) {
G.a[10 * i + j][10 * i + j + 1] = 1;
}
}
G = Pow(G, k);
cout << G.a[0][(n - 1) * 10] << endl;
return 0;
}