 The recursion is obvious ... But if you want to do matrix multiplication, you have to split the points .. At first, I was very confused about every weight v>1 All sides are new v-1 There are two nodes to transfer ... And then TLE 了 ... Break each point into 9 Just one ... Time complexity O((9N)^3*logT)

--------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 900;
const int MOD = 2009;
const int lim = 46300;

typedef int MATRIX[maxn][maxn];

MATRIX mat, Q, tmp;
int N, T, V, Id[maxn];
char s[maxn];

inline void upd(int &x, int t) {
if((x += t) >= lim) x %= MOD;
}

void MUL(MATRIX& A, MATRIX& B) {
memset(tmp, 0, sizeof tmp);
for(int i = 0; i < V; i++)
for(int k = 0; k < V; k++)
for(int j = 0; j < V; j++)
upd(tmp[i][j], A[i][k] * B[k][j]);
memcpy(A, tmp, sizeof A);
}

int main() {
scanf("%d%d", &N, &T);
V = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j < 9; j++)
Id[i][j] = V++;
memset(mat, 0, sizeof mat);
for(int i = 0; i < N; i++) {
scanf("%s", s);
for(int j = 0; j < N; j++)
if(s[j] > '0') mat[Id[j]][Id[i][s[j] - '1']] = 1;
}
for(int i = 0; i < N; i++)
for(int j = 1; j < 9; j++)
mat[Id[i][j]][Id[i][j - 1]] = 1;
memset(Q, 0, sizeof Q);
for(int i = 0; i < V; i++) Q[i][i] = 1;
for(; T; T >>= 1, MUL(mat, mat))
if(T & 1) MUL(Q, mat);
printf("%d\n", Q[Id[N - 1]] % MOD);
return 0;
}

--------------------------------------------------------------------------

1297: [SCOI2009] Get lost

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 857  Solved: 602
[Submit][Status][Discuss]

Description

windy Lost in digraph . The directed graph has N Nodes ,windy From the node 0 set out , He has to happen to be T Time to node N-1. Now let's give the digraph , You can tell windy How many different paths are there in all ？ Be careful ：windy Can't linger on a node , And the time passing through a directed edge is strictly a given time .

Input

The first line contains two integers ,N T. Next there is N That's ok , One length per line is N String . The first i Xing di j As a '0' Represents slave node i To the node j There is no side . by '1' To '9' Represents slave node i To the node j It takes time .

Output

Contains an integer , Number of possible paths , This number can be very large , Just output this number divided by 2009 The remainder of .

Sample Input

【 Enter sample one 】
2 2
11
00

【 Enter example 2 】
5 30
12045
07105
47805
12024
12345

Sample Output

【 Output sample one 】
1

【 Examples explain one 】
0->0->1

【 Output sample 2 】
852

HINT

30% The data of , Satisfy 2 <= N <= 5 ; 1 <= T <= 30 .
100% The data of , Satisfy 2 <= N <= 10 ; 1 <= T <= 1000000000 .

BZOJ 1297: [SCOI2009] Get lost ( dp + Matrix fast power ) More articles about

1. 【BZOJ1297】[SCOI2009] Get lost （ Matrix fast power ）

[BZOJ1297][SCOI2009] Get lost ( Matrix fast power ) Topic BZOJ Luogu Answer key Because the biggest edge weight is $$9$$, So the record goes forward $$9$$ Unit time ago . Just the number of solutions to each point , So the matrix size is \ ...

2. 2018.10.23 bzoj1297: [SCOI2009] Get lost （ Matrix fast power optimization dp）

Portal Matrix fast power optimization dp Simple questions . Consider the state transfer equation : f[time][u]=∑f[time−1][v]f[time][u]=\sum f[time-1][v]f[time][u]=∑f[time−1 ...

3. 【BZOJ】2004: [Hnoi2010]Bus Bus lines Pressure DP+ Matrix fast power

[ The question ]n The points are equidistant in length n-1 In a straight line , Starting point 1~k There's a bus , Every bus needs some stops , Each point can only be stopped by one bus at most , And the distance between two adjacent stops of each bus is at most p, All the buses will stop at n-k+1~n ...

4. 【BZOJ】4861: [Beijing2017] Magic spell AC automata +DP+ Matrix fast power

[ The question ] Given n Two original strings and m A taboo string , It is required to use the original string set to spell the string without taboo and the length is L The number of strings .(60%)n,m<=50,L<=100.(40%) The length of the original string is 1 or 2,L<=10^18. [ Algorithm ...

5. bnuoj 34985 Elegant String DP+ Matrix fast power

Topic link :http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=34985 We define a kind of strings as elegant s ...

6. HDU 5434 Peace small elephant Pressure dp+ Matrix fast power

Topic link : http://acm.hdu.edu.cn/showproblem.php?pid=5434 Peace small elephant  Accepts: 38  Submissions: ...

7. BZOJ5298 CQOI2018 Staggered sequence 【DP+ Matrix fast power optimization 】*

BZOJ5298 CQOI2018 Staggered sequence [DP+ Matrix fast power optimization ] Description We call it just by 0.1 The sequence of composition is " Staggered sequence ", If and only if there is no adjacent 1( There can be adjacency ...

8. Codeforces 621E Wet Shark and Block【dp + Matrix fast power 】

The question : Yes b individual blocks, Every blocks There are n A the same 0~9 The number of , If from the first block choose 1, From the second block choose 2, So it's made up of 12, Ask for a given n,b How many kinds of composition schemes make the final mold x The remainder is k. branch ...

9. codeforces E. Okabe and El Psy Kongroo（dp+ Matrix fast power ）

Topic link :http://codeforces.com/contest/821/problem/E The question : We are now in (0,0) It's about , The goal is to go to (K,0) It's about . Every time we can get from (x,y) Go to the (x+1,y- ...

Random recommendation

1. EF framework ~ stay T4 Custom attributes in template getter and setter

Back to directory T4 Template for us in ORM Convenient operation is provided , It is very convenient to modify the entity globally , I introduced it before T4 To add default to attributes , And today I'm going to tell you how to use T4 The template will getter,setter Change the block to yourself ...

2. cmd Open the control panel and other commands

If you're on the machine of a domain user with less privileges , To do some management operations , It's inevitable to use cmd Open some programs that can only be opened in the graphical interface before . Here are some common operations I collected . Start the program in some capacity :runas /user:it\n1 ...

3. C The preparation before basic language learning -1

C Language Overview Welcome to C The world of !C The name of language is C, Because C Language comes from Ken Thompson Invented B Language . It's a portable language , Usually a C Programs can run on other systems with little or no changes : It's powerful ...

4. Node.js Learning starts

Node.js Study : To put it simply Node.js It's running on the server side JavaScript.Node.js It's based on Chrome JavaScript A platform built at runtime .Node.js It's an event ...

5. establish .ignore file

Method 1 :1. When you need to create .gitignore File folder , The right choice Git Bash Go to the command line , Enter the project directory . Such as :(cd /d/git/project) 2. Input touch .gitig ...

6. Cron Expression details （ It has been sorted out 、 Very clear ）

Cron An expression is a string , String is divided into 6 or 7 Domains , Each domain represents a meaning ,Cron There are two grammatical formats as follows : Seconds Minutes Hours DayofMonth Month DayofWeek ...

7. BZOJ 4610: [Wf2016]Ceiling Functi Water problem

4610: [Wf2016]Ceiling Functi Topic linking : http://www.lydsy.com/JudgeOnline/problem.php?id=4610 Description ...

8. opencv load modify preservation Images

#include <opencv2/opencv.hpp> #include <iostream> using namespace cv; /* 1 Load image cv::imre ...

9. ubuntu The structures, openGL Environmental Science

1.       Build a basic compilation environment sudo apt-get install build-essential 2.       install OpenGL Library sudo apt-get install ...

10. JavaScript Flow of events -- Event Bubbling 、 Target and event capture

1. Event Bubbling Microsoft came up with an event stream called event bubble . Bubbling can be likened to throwing a stone into the water , Bubbles will come out of the water all the time . in other words , Events start with the innermost elements , All the way up , until document object . because ...