C++(g++ 7.5.0) 解法, 执行用时: 145ms, 内存消耗: 640K, 提交时间: 2022-08-29 21:42:31

#include<cstdio>
const int mod=2009;
struct Matrix
{
	int **ele,n,m;
	Matrix()=delete;
	Matrix(int n0):n(n0),m(n0){ele=new int*[n];for(int i=0,*p;i<n;i++)*(ele+i)=new int[m];}
	Matrix(int n0,int m0):n(n0),m(m0){ele=new int*[n];for(int i=0,*p;i<n;i++)*(ele+i)=new int[m];}
	Matrix(const Matrix&A):n(A.n),m(A.m)
	{	
		ele=new int*[n];
		for(int i=0,*p;i<n;i++)*(ele+i)=new int[m];
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)ele[i][j]=A.ele[i][j];
	}
	~Matrix(){for(int i=0;i<n;i++)delete[]*(ele+i);delete[]ele;}
	Matrix&clear(){for(int i=0;i<n;i++)for(int j=0;j<m;j++)ele[i][j]=0;return*this;}
	Matrix&clear_one(){for(int i=0;i<n;i++)for(int j=0;j<m;j++)ele[i][j]=i==j;return*this;}
	Matrix&forall(int*x){for(int i=0;i<n;i++)for(int j=0;j<m;j++,x++)ele[i][j]=*x;return*this;}
	Matrix&input(){for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&ele[i][j]);return*this;}
	Matrix&print(){for(int i=0;i<n;i++,putchar(10))for(int j=0;j<m;j++)printf("%d ",ele[i][j]);return*this;}
	Matrix&operator=(const Matrix&A)
	{
		n=A.n,m=A.m;
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)ele[i][j]=A.ele[i][j];
		return *this;
	}
	friend Matrix operator^(Matrix A,long long b)//快速幂 
	{
		Matrix C(A.n,A.n);C.clear_one();
		while(b)
		{
			if(b&1)C=C*A;
			A=A*A,b>>=1;
		}
		return C;
	}
	friend Matrix operator*(const Matrix&A,const Matrix&B)
	{
		int n=A.n,s=B.n,m=B.m;
		Matrix C(n,m);C.clear();
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)
			for(int k=0;k<s;k++)C.ele[i][j]=(1ll*A.ele[i][k]*B.ele[k][j]+C.ele[i][j])%mod;
		return C;
	}
	friend Matrix operator+(const Matrix&A,const Matrix&B)
	{
		Matrix C(A.n,A.m);
		for(int i=0;i<A.n;i++)for(int j=0;j<A.m;j++)C.ele[i][j]=A.ele[i][j]+B.ele[i][j];
		return C;
	}
	friend Matrix operator-(const Matrix&A,const Matrix&B)
	{
		Matrix C(A.n,A.m);
		for(int i=0;i<A.n;i++)for(int j=0;j<A.m;j++)C.ele[i][j]=A.ele[i][j]-B.ele[i][j];
		return C;
	}
};
int main()
{
	int n,t;scanf("%d%d",&n,&t);
	Matrix J(n*9,n*9);J.clear();
	for(int i=0;i<n;i++)
	{
		for(int j=n+i;j<9*n;j+=n)
			J.ele[j][j-n]=1;
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)
	{
		char c;scanf(" %c",&c);
		if(c!='0')J.ele[i][j+(c-'1')*n]=1;
	}
//	for(int i=0;i<9*n;i++)for(int j=0;j<9*n;j++)if(J.ele[i][j])printf("%d->%d\n",i,j);
	printf("%d",(J^t).ele[0][n-1]);
	return 0;
}

C++ 解法, 执行用时: 297ms, 内存消耗: 884K, 提交时间: 2022-04-07 20:30:39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,t;
const ll mod = 2009;
struct node
{
	int a[170][170];
	node operator * (node b)
	{
		node x;
		memset(x.a, 0, sizeof(x.a));
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				for (int k = 1; k <= n; k++)
				{
					x.a[i][j] += b.a[i][k] * a[k][j];
					x.a[i][j] %= mod;
				}
			}
		}
		return x;
	}
};
int main()
{
	cin >> n >> t;
	int loc = n;
	node res;
	memset(res.a, 0, sizeof(res.a));
	char c;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> c;
			if (c - '0')
			{
				res.a[i * 10 + c - '0'][j * 10 + 1] = 1;
			}
			for (int k = 1; k < c - '0'; k++)
			{
				res.a[i * 10 + k][i * 10 + k + 1] = 1;
			}
		}
	}
	node ans;
	n = n * 10 + 10;
	memset(ans.a, 0, sizeof(ans.a));
	for (int i = 1; i <= n; i++)ans.a[i][i] = 1;
	while (t)
	{
		if (t & 1)ans = ans * res;
		res = res * res;
		t >>= 1;
	}
	cout << ans.a[11][loc * 10 + 1] << endl;
}

C++14(g++5.4) 解法, 执行用时: 207ms, 内存消耗: 724K, 提交时间: 2020-08-05 17:59:09

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=2009;
int n,x,t; 
struct mat{
	int a[105][105];
}m,u;
mat matmul(mat c,mat d){
	int h=n*10;
	mat tmp;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=h;j++){
			tmp.a[i][j]=0;
			for(int k=1;k<=h;k++)
				tmp.a[i][j]=(tmp.a[i][j]+c.a[i][k]*d.a[k][j]%mod)%mod;
		}
	return tmp;		
}
void matpow(int b){
	for(int i=1;i<=9*n;i++)u.a[i][i]=1;
	while(b){
		if(b&1)u=matmul(u,m);
		m=matmul(m,m);
		b>>=1;
	}
	printf("%d",u.a[1][n]);
}
int main(){
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=8;j++)m.a[i+j*n][i+n*(j-1)]=1;
		for(int j=1;j<=n;j++){
			scanf("%1d",&x);
			if(!x)continue;
			m.a[i][j+n*(x-1)]=1;
		}
	}
	matpow(t);
	return 0;
}