1386 - Cellular Automaton
Moderator: Board moderators
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
1386 - Cellular Automaton
Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!
-
Repon kumar Roy
- Learning poster
- Posts: 96
- Joined: Tue Apr 23, 2013 12:54 pm
Re: 1386 - Cellular Automaton
Matrix Exponentiation, But need to optimize
Here the matrix is cyclic
Let's say this n=5,d=1
[1 1 0 0 1 ]
[1 1 1 0 0]
[0 1 1 1 0]
[0 0 1 1 1]
If we can determine first row of this matrix, we can generate the other row.
So we need to keep only thee first row of this matrix and multiply with only to get the first row.
Here the matrix is cyclic
Let's say this n=5,d=1
[1 1 0 0 1 ]
[1 1 1 0 0]
[0 1 1 1 0]
[0 0 1 1 1]
If we can determine first row of this matrix, we can generate the other row.
So we need to keep only thee first row of this matrix and multiply with only to get the first row.