Another purple question!
Topic description
There is a chessboard with \(n\) rows and \(m\) columns, and a horse wants to jump from the upper left corner of the chessboard to the lower right corner. At each step it jumps to the right by an odd column and to the current or adjacent row. During the jump, the horse cannot leave the board. For example, when \(n = 3\), \(m = 10\), the following figure is a feasible jump method.
Try to find the result of taking the number of jumps modulo \(30\,011\).
input format
There is only one line, containing two positive integers \(n, m\), indicating the size of the chessboard.
output format
There is only one line, containing an integer, that is, the result of the jump method modulo \(30\,011\).
Example #1
Sample Input #1
3 5
Sample output #1
10
hint
- For data of \(10\%\), \(1 \leq n \leq 10\), \(2 \leq m \leq 10\);
- For \(50\%\) data, \(1 \leq n \leq 10\), \(2 ≤ m ≤ 10^5\);
- For data of \(80\%\), \(1 \leq n \leq 10\), \(2 \leq m \leq 10^9\);
- For \(100\%\) data, \(1 \leq n \leq 50\), \(2 \leq m \leq 10^9\).
Ideas section
first sight
Idea 1
It's a super simple dp question
For the point (2, 5) (blue box), it can be transferred from the sum of the numbers in the yellow box in the figure (the horse at the position of the yellow box can jump to the blue box), And the yellow box is an odd column away from the blue box, then we can think of a simplest dp transfer equation
Attach a code that will time out
#include<bits/stdc++.h>
using namespace std;
int n,m,a[60][1000000];
int mod=3011;
int main(){
// freopen("jump.in","r",stdin);
freopen("jump1.out","w",stdout);
scanf("%d%d",&n,&m);
a[1][1]=1;
for(int j=2;j<=m;j++){
for(int i=1;i<=n;i++){
for(int k=1;k<j;k+=2){
a[i][j]=(a[i][j]+a[i+1][j-k]);
a[i][j]=(a[i][j]+a[i][j-k]);
a[i][j]=(a[i][j]+a[i-1][j-k]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<setw(7)<<a[i][j];
}
cout<<endl;
}
return 0;
}
However, you will find a very serious problem. It seems that the array can't be opened that big, and another serious problem is that it will time out (the complexity is too high)! ! ! It's over, this algorithm is useless
Since then, this code has been reduced to a shooting tool...
second look
Idea 2
Let's tackle the complexity problem first. The easiest way is of course the prefix sum.
The prefix sum is actually very easy to think of, because every time we get the answer of a point, we will find the answer of the odd line forward to calculate, we only need to count the prefix sum of the answers of the previous odd lines to save this step.
Every time we calculate a new answer, we accumulate the answer into the prefix sum, and each time we only need to access the adjacent row in the prefix sum.
Attach the code that will time out again
(I wrote this for the exam, but it's TLE)
#include<bits/stdc++.h>
using namespace std;
long long n,m;//a[60][1000000];
long long a1[60],a2[60],now[60];
int mod=30011;
int main(){
// freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
scanf("%d%d",&n,&m);
a1[1]=a2[1]=a2[2]=1;
for(int j=3;j<=m;j++){
if(j%2==1){//from a2
for(int i=1;i<=n;i++){
now[i]=(a2[i-1]+a2[i]+a2[i+1])%mod;
a1[i]=(a1[i]+now[i])%mod;//putin a1
// cout<<setw(10)<<now[i];
}
// cout<<endl;
}
else{//from a1
for(int i=1;i<=n;i++){
now[i]=(a1[i-1]+a1[i]+a1[i+1])%mod;
a2[i]=(a2[i]+now[i])%mod;//putin a2
// cout<<setw(10)<<now[i];
}
// cout<<endl;
}
}
printf("%d",now[n]);
return 0;
}
Because each time the answer is obtained from an odd-numbered column, we need to record two prefix sums, one for odd-numbered columns and one for even-numbered columns (array a1 and array a2)
However, the cruel truth is that it timed out again, and the algorithm became a matchmaking tool again...
Third look - it's finally correct!
ideas
Is there any other way we can count prefix sums like this?
That's for sure. (Isn't that the correct solution?)
We change the transfer equation to this:
Draw a picture to explain:
With this picture, it is clear at a glance. First of all, the three adjacent numbers in the previous column need to be added, and then, the columns separated by three columns, five columns, and even further away are included by the number that is separated by two columns in the same row, so we just It is obvious that this transfer equation is obtained.
After talking about the transfer equation, how should we write it? That's of course the acceleration of the matrix (to be honest, I didn't expect it at all at the beginning)
For our new column, we need to transfer from the previous two rows, so the initial matrix is obtained:
This is for the case when n is equal to 4 (the first 4 elements are in the second column, the last 4 elements are in the first column):
The first n elements are elements separated by one column, and n+1 to 2*n elements are elements separated by two columns
At this time, it is time to build the transition matrix: (the matrix should be a square matrix of size 2n*2n)
We're going to turn this initial matrix into a matrix with elements in the third and second columns:
It is easy to deduce this transition matrix from above (the above picture is for the case where n is equal to 4), we only need to calculate according to the transition matrix given above for each element of the third column (provided that you already know matrix multiplication)
It looks like this question has already been done! However, the display is cruel, and you will find that your answer is wrong.
wrong place
After you debug seriously, you will magically find that the answer in the first row of the third column seems to be wrong (the wrong answer will be like this (as shown below))
This is because when we transfer the element in the first row of the third column, the elements on 1 and 1 will also be added. However, according to the meaning of the question, this point will not be counted in the points 1 and 3.
So this is a special case (most of the practice on the Internet is to subtract something (it seems to be a prefix sum, but I didn't understand it)), I am very straightforward here to directly change the initial matrix from the 4th column and the 3rd column column start, which directly avoids this magic problem:
Then we only need to judge the case where m is less than or equal to 4 and n is less than or equal to 4 (later, we will know from the discussion of others, this special judgment can also avoid some magical errors (such as 50, 2 will output a magical 1))
In this case, we can just use the fast power m-4 times
final code
#include<bits/stdc++.h>
using namespace std;
struct matrix{
long long h,l;//h for row, l for column
int a[110][110];
}ans,wns;
long long n,m;
int mod=30011;
matrix times(matrix r,matrix c){
matrix timesans;
memset(timesans.a,0,sizeof(timesans.a));
timesans.h=r.h;
timesans.l=c.l;
for(int i=1;i<=r.h;i++){
for(int j=1;j<=c.l;j++){
for(int q=1;q<=r.l;q++){
timesans.a[i][j]=(timesans.a[i][j]+r.a[i][q]%mod*c.a[q][j]%mod)%mod;
}
}
}
return timesans;
}
matrix mul(matrix x,long long y){
matrix res;
res.h=res.l=x.l;
memset(res.a,0,sizeof(res.a));
for(int i=1;i<=res.l;i++){
res.a[i][i]=1;
}
for(;y;y>>=1){
if(y&1) res=times(x,res);
x=times(x,x);
}
return res;
}
matrix buildansup4(long long n){
matrix temp;
memset(temp.a,0,sizeof(temp.a));
temp.h=1;
temp.l=2*n;
temp.a[1][1]=5;
temp.a[1][2]=6;
temp.a[1][3]=3;
temp.a[1][4]=1;
temp.a[1][n+1]=2;
temp.a[1][n+2]=2;
temp.a[1][n+3]=1;
return temp;
}
matrix buildans3(){
matrix temp;
memset(temp.a,0,sizeof(temp.a));
temp.h=1;
temp.l=6;
temp.a[1][1]=5;
temp.a[1][2]=6;
temp.a[1][3]=3;
temp.a[1][4]=2;
temp.a[1][5]=2;
temp.a[1][6]=1;
return temp;
}
matrix buildans2(){
matrix temp;
memset(temp.a,0,sizeof(temp.a));
temp.h=1;
temp.l=4;
temp.a[1][1]=5;
temp.a[1][2]=5;
temp.a[1][3]=2;
temp.a[1][4]=2;
return temp;
}
matrix buildans1(){
matrix temp;
memset(temp.a,0,sizeof(temp.a));
temp.h=1;
temp.l=2;
temp.a[1][1]=2;
temp.a[1][2]=1;
return temp;
}
matrix buildwns(long long n){
matrix temp;
temp.l=temp.h=2*n;
memset(temp.a,0,sizeof(temp.a));
for(int i=1;i<=n;i++){
temp.a[i][i]=1;
if(i-1>=1){
temp.a[i][i-1]=1;
}
if(i+1<=n){
temp.a[i][i+1]=1;
}
}
for(int i=1;i<=n;i++){
temp.a[i][n+i]=1;
}
for(int i=n+1;i<=2*n;i++){
temp.a[i][i-n]=1;
}
return temp;
}
void printmatrix(matrix p){
for(int i=1;i<=p.h;i++){
for(int j=1;j<=p.l;j++){
cout<<p.a[i][j]<<" ";
}
cout<<endl;
}
}
int main(){
cin>>n>>m;
if(m<=4){
if(m==4){
if(n==1){
cout<<5;
return 0;
}
if(n==2){
cout<<6;
return 0;
}
if(n==3){
cout<<3;
return 0;
}
if(n==4){
cout<<1;
return 0;
}
}
if(m==3){
if(n==1){
cout<<2;
return 0;
}
if(n==2){
cout<<2;
return 0;
}
if(n==3){
cout<<1;
return 0;
}
}
if(m==2){
if(n==1){
cout<<1;
return 0;
}
if(n==2){
cout<<1;
return 0;
}
}
if(m==1){
if(n==1){
cout<<1;
return 0;
}
}
cout<<0;
return 0;
}
if(n>=4){
ans=buildansup4(n);
}
if(n==3){
ans=buildans3();
}
if(n==2){
ans=buildans2();
}
if(n==1){
ans=buildans1();
}
wns=buildwns(n);
// printmatrix(wns);
// system("pause");
wns=mul(wns,m-4);
ans=times(ans,wns);
printf("%lld",ans.a[1][n]%mod);
// printmatrix(ans);
return 0;
}
little problem
I encountered a magical problem. In the last code, if the variable definitions on lines 5 and 8 are longlong, the 11th point of his luogu evaluation will actually be TLE (I am full of doubts)
I don't know why, after I changed these two variables to int, the 11th point passed... I really don't know why (it feels very metaphysical)
If anyone knows where the problem is, please leave a message in the comment area