迷路

C++(g++ 7.5.0) 解法, 执行用时: 65ms, 内存消耗: 584K, 提交时间: 2022-08-27 20:33:55

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 2009;
const int N = 100 + 5;
ll n, t;

struct node{
    int s[N][N];
}res, mat;

void matrixI(node &e)
{
    for (int i = 1; i <= n * 9; ++i)
        for (int j = 1; j <= n * 9; ++j)
            e.s[i][j] = (i == j);
}

void matrixMuti(node &x, node &y, node &z)
{
    memset(z.s, 0, sizeof(z.s));
    
    for (int i = 1; i <= n * 9; ++i)
        for (int j = 1; j <= n * 9; ++j)
            if(x.s[i][j])
                for (int k = 1; k <= n * 9; ++k)
                    z.s[i][k] = (z.s[i][k] + x.s[i][j] * y.s[j][k]) % mod;
}

void pow_fast(ll k)
{
    matrixI(res);
    node tmp = mat, t;
    
    while (k)
    {
        if (k & 1)
        {
            matrixMuti(res, tmp, t);
            res = t;
        }
        matrixMuti(tmp, tmp, t);
        tmp = t;
        
        k >>= 1;
    }
}

int main()
{
    scanf("%lld %lld", &n, &t);
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < 9; ++j)
            mat.s[9 * (i - 1) + j][9 * (i - 1) + j + 1] = 1;
    
    char str[100];
    
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", str);
        
        for (int j = 1; j <= n; ++j)
            if (str[j - 1] > '0')
                mat.s[9 * (i - 1) + str[j - 1] - '0'][9 * (j - 1) + 1] = 1;
    }
    
    pow_fast(t);
    
    printf("%d\n", res.s[1][9 * n - 8]);
    
    return 0;
}

Java(javac 1.8) 解法, 执行用时: 661ms, 内存消耗: 14156K, 提交时间: 2020-05-03 22:36:46

import java.util.Scanner;

public class Main {
	static int N;
	static int mod = 2009;

	public static long[][] matrixMultiply(long[][] a, long[][] b) {
		long[][] res = new long[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
				}
			}
		}
		return res;
	}

	public static long[][] matrixFastPow(long[][] a, long k) {
		long[][] res = new long[N][N];
		for (int i = 0; i < N; i++) {
			res[i][i] = 1;
		}
		while (k > 0) {
			if (k % 2 == 1) {
				res = matrixMultiply(res, a);
			}
			a = matrixMultiply(a, a);
			k >>= 1;
		}
		return res;
	}

	public static int pos(int i, int j) {
		return i * 9 + j;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int t = sc.nextInt();
		N = n * 9;
		long[][] a = new long[N][N];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 8; j++) {
				a[pos(i, j)][pos(i, j + 1)] = 1;
			}
			char[] s = sc.next().toCharArray();
			for (int j = 0; j < n; j++) {
				if (s[j] > '0') {
					a[pos(i, s[j] - '0' - 1)][pos(j, 0)] = 1;
				}
			}
		}
		long[][] multiply = matrixFastPow(a, t);
		System.out.println(multiply[0][(n - 1) * 9]);
	}
}

C++14(g++5.4) 解法, 执行用时: 212ms, 内存消耗: 588K, 提交时间: 2020-02-17 17:08:25

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

const int MOD=2009;

typedef vector<vector<int>> Matrix;

Matrix operator*(const Matrix &A, const Matrix & B) {
  Matrix C(A.size(), vector<int>(B[0].size()));
  for (size_t i = 0; i < A.size(); i++) {
    for (size_t j = 0; j < B[0].size(); j++) {
      for (size_t k = 0; k < A[0].size(); k++) (C[i][j] += 1ll*A[i][k] * B[k][j])%=MOD;
    }
  }
  return C;
}

Matrix powMod(Matrix A, int x) {
  Matrix S(A.size(), vector<int>(A.size()));
  for (size_t i = 0; i < S.size(); i++) S[i][i] = 1;
  while (x) {
    if (x % 2) S = S * A;
    A = A * A;
    x /= 2;
  }
  return S;
}

int main() {
  int N, T; cin >> N >> T;
  vector<string> grid(N); for (auto &g: grid) cin >> g;
  Matrix A(N*10, vector<int>(N*10));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 9; j++) {
      A[i+(j+1)*N][i+j*N] = 1;
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int t = grid[i][j] - '0' - 1;
      if (t < 0) continue;
      A[i][j+t*N] = 1;
    }
  }
  auto C = powMod(A, T);
  cout << C[0][N-1] << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 209ms, 内存消耗: 620K, 提交时间: 2020-06-02 11:31:15

#include<bits/stdc++.h>
using namespace std;
const int MOD=2009;
typedef vector<vector<int> > Matrix;
Matrix operator *(const Matrix &A,const Matrix &B)
{
	Matrix C(A.size(),vector<int>(B[0].size()));
	for(size_t i=0;i<A.size();i++)
	{
		for(size_t j=0;j<B[0].size();j++)
		{
			for(size_t k=0;k<A[0].size();k++)
			(C[i][j]+=1ll*A[i][k]*B[k][j])%=MOD;
		}
	}
	return C;
 }
 Matrix powMod(Matrix A,int x)
 {
 	Matrix S(A.size(),vector<int>(A.size()));
 	for(size_t i=0;i<S.size();i++)
 	S[i][i]=1;
 	while(x)
 	{
 		if(x%2) S=S*A;
 		A=A*A;
 		x/=2;
	 }
	 return S;
 }
 int main()
 {
 	int N,T;
 	cin>>N>>T;
 	vector<string> grid(N);
 	for(auto &g:grid)
 	cin>>g;
 	Matrix A(N*10,vector<int>(N*10));
 	for(int i=0;i<N;i++)
 	{
 		for(int j=0;j<9;j++)
 		{
 			A[i+(j+1)*N][i+j*N]=1;
		 }
	 }
	 for(int i=0;i<N;i++)
	 {
	 	for(int j=0;j<N;j++)
	 	{
	 		int t=grid[i][j]-'0'-1;
	 		if(t<0)
	 		continue;
	 		A[i][j+t*N]=1;
		 }
	 }
	 auto C=powMod(A,T);
	 cout<<C[0][N-1]<<endl;
 }

pypy3(pypy3.6.1) 解法, 执行用时: 562ms, 内存消耗: 25308K, 提交时间: 2021-05-09 23:25:24

def chen(a,b):
    ans=[[0 for j in range(len(b[i]))] for i in range(len(a))]
    for i in range(len(ans)):
        for j in range(len(ans[i])):
            ans[i][j]=sum((a[i][k]*b[k][j] for k in range(len(b))))%2009
    return ans
beishu=9
n,t=(int(i) for i in input().split())
mm=[[int(i)for i in input()]for j in range(n)]
m=[[0 for i in range(beishu*n)] for j in range(beishu*n)]
for i in range(n):
    for j in range(n):
        w=mm[i][j]
        if w!=0:
            m[beishu*i+w-1][beishu*j]=1
        for c in range(beishu-1):
            m[beishu*i+c][beishu*i+c+1]=1
tt=[(t>>i)&1 for i in range(40)  if t>>i!=0]
ans=[[1 if i==j else 0 for i in range(beishu*n)] for j in range(beishu*n)]
for i in tt:
    if i==1:
        ans=chen(m,ans)
    m=chen(m,m)
print(ans[0*beishu][(n-1)*beishu]%2009)

详情