Topic requirements:
Use 1*2 dominoes to completely cover the n*m chessboard, how many solutions are there
1<=n<=5,1<=m<=10^18
The answer is 998244353 modulo
train of thought
You can think that my dotted line is nonsense, I thought about it for two days and finally figured it out, I am a rookie
In general, it is matrix fast power plus state compression dp
#include <bits/stdc++.h> #define int long long using namespace std; const int N=5, M=1<<N, mod=998244353; int n,m; bool st[M]; int A[M][M],tmp[M][M],res[M][M]; void MXMP(int a[][M], int b[][M]) { memset(tmp, 0, sizeof tmp);//tmp is used to store the multiplication result for (int i = 0; i < (1<<n); i ++ ) { for (int j = 0; j < (1<<n); j ++ ) { for (int k = 0; k < (1<<n); k ++ ) { tmp[i][j] = (tmp[i][j] + (a[i][k] * b[k][j]) % mod) % mod;//Remember to touch mod } } } for (int i = 0; i < (1<<n); i ++ ) { for (int j = 0; j < (1<<n); j ++ ) { a[i][j] = tmp[i][j];//Remember to assign tmp to a } } } void powermod(int A[][M], int x) { memset(res, 0, sizeof res);//res stores the result for (int i = 0; i < (1<<n); i ++ ) { for (int j = 0; j < (1<<n); j ++ ) { res[i][j] = A[i][j]; } } while (x) { if (x & amp; 1) MXMP(res, A);//x is an odd number, multiply A by res MXMP(A, A);//Multiply A itself x >>= 1;//x divided by two } for (int i = 0; i < (1<<n); i ++ ) {//assign the result to A for (int j = 0; j < (1<<n); j ++ ) { A[i][j] = res[i][j]; } } } signed main() { ios_base::sync_with_stdio(0); cin. tie(0), cout. tie(0); cin>>n>>m; if((n & amp;1) & amp; & amp;(m & amp;1)){//judging whether they are all odd numbers cout<<0; return 0; } memset(st,true,sizeof st);//Whether the record can be placed for(int i=0;i<(1<<n);i ++ ){ int cnt=0; for(int j=0;j<n;j++){ if((i>>j) & amp;1){ if(cnt & amp;1){ st[i]=false; break; } }else cnt++; } if(cnt & amp;1) st[i]=false; } memset(A,0,sizeof A); for(int j=0;j<(1<<n);j++ ){ for(int k=0;k<(1<<n);k ++ ){ if((j & amp;k)==0 & amp; & amp;st[j|k]){ A[j][k]=1; //Which state can the record be inherited from? } } } m-=1;//Because res is assigned by A, res*A will count one more time and subtract one powermod(A,m);//Matrix fast power cout<<A[0][0]; /*for(int i=0;i<(1<<n);i + + ){ for(int j=0;j<(1<<n);j++ ){ cout<<A[i][j]<<' '; } cout<<'\\ '; }*/ \t }
————————————————– ————————————————– —————————–
I didn’t look at the scope and thought it was just a simple state compression. The dp was very happy to type it up according to the version, and it timed out after sending it in.
Looking at the range 10 to the 18th power later, it was not done during the competition
Here is the code for state compressed dp (timeout)
#include <bits/stdc++.h> #define int long long using namespace std; const int N=5,M=1<<N; int n,m; bool st[M]; int f[M][M]; signed main() { ios_base::sync_with_stdio(0); cin. tie(0), cout. tie(0); cin>>n>>m; memset(st, true, sizeof st); for(int i=0;i<(1<<n);i ++ ){ int cnt=0; for(int j=0;j<n;j++){ if((i>>j) & amp;1){ if(cnt & amp;1){ st[i]=false; break; } }else cnt++; } if(cnt & amp;1) st[i]=false; } memset(f,0,sizeof f); f[0][0]=1; for(int i=1;i<=m;i + + ){ for(int j=0;j<(1<<n);j++ ){ for(int k=0;k<(1<<n);k ++ ){ if((j & amp;k)==0 & amp; & amp;st[j|k]){ f[i][j] + =f[i-1][k]; } } } } cout<<f[m][0]; }
Later, we still found the law when n=1 is 0,1,0,1,0,1
n=2 is 1,2,3,5,8,13
It is found that it is a Fibonacci sequence. At this time, m can be obtained to 10^18. The normal search will definitely time out, but Fibonacci can also be used to quickly exponentiate the matrix. At this time, I have a general idea. Is it the whole? can be optimized with matrix fast exponentiation
matrix fast exponentiation
The following is the code for finding Fibonacci
#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 998244353; int A[2][2] = { {1,1},{1,0} }; int res[2][2], n; int tmp[2][2]; void MXMP(int a[][2], int b[][2]) { memset(tmp, 0, sizeof tmp); for (int i = 0; i < 2; i ++ ) { for (int j = 0; j < 2; j ++ ) { for (int k = 0; k < 2; k ++ ) { tmp[i][j] = (tmp[i][j]%mod + (a[i][k] * b[k][j]) % mod) % mod; } } } for (int i = 0; i < 2; i ++ ) { for (int j = 0; j < 2; j ++ ) { a[i][j] = tmp[i][j]%mod; } } } void powermod(int A[][2], int x) { memset(res, 0, sizeof res); for (int i = 0; i < 2; i ++ ) { for (int j = 0; j < 2; j ++ ) { res[i][j] = 1; } } while (x) { if (x & 1) MXMP(res, A); MXMP(A, A); x >>= 1; } for (int i = 0; i < 2; i ++ ) { for (int j = 0; j < 2; j ++ ) { A[i][j] = res[i][j]; } } } signed main() { ios_base::sync_with_stdio(0); cin. tie(0), cout. tie(0); cin >> n; n-=1; if(n==0||n==1){ cout<<1; return 0; } powermod(A, n - 2); int q = (A[0][1] + A[0][0])%mod; cout << q; }
Then my n=3 is 1, 0, 3, 0, 11, 0
I want to find the law of even numbers first.
Then I went to find n=4 1,1,5,11,36,95,281
Look at the law of appearance of other numbers and then deduce which number is inherited from
I wrote down the numbers where the numbers appeared
Looking at the picture above, 1 can be added to 12456, and 2 can be added to 12.
Later, I thought that I could use the matrix, which is the picture on the right.
Can be written as n==4 code
#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 998244353; int A[6][6] = { {1,1,0,1,1,1},{1,1,0,0,0,0},{0,0,0,1,0,0 },{1,0,1,0,0,0},{1,0,0,0,1,0},{1,0,0,0,0,0}}; int res[6][6], n; int tmp[6][6]; void MXMP(int a[][6], int b[][6]) { memset(tmp, 0, sizeof tmp); for (int i = 0; i < 6; i ++ ) { for (int j = 0; j < 6; j ++ ) { for (int k = 0; k < 6; k ++ ) { tmp[i][j] = (tmp[i][j] + (a[i][k] * b[k][j]) % mod) % mod; } } } for (int i = 0; i < 6; i ++ ) { for (int j = 0; j < 6; j ++ ) { a[i][j] = tmp[i][j]; } } } void powermod(int A[][6], int x) { memset(res, 0, sizeof res); for (int i = 0; i < 6; i ++ ) { for (int j = 0; j < 6; j ++ ) { res[i][j] = A[i][j]; } } while (x) { if (x & 1) MXMP(res, A); MXMP(A, A); x >>= 1; } for (int i = 0; i < 6; i ++ ) { for (int j = 0; j < 6; j ++ ) { A[i][j] = res[i][j]; } } } signed main() { ios_base::sync_with_stdio(0); cin. tie(0), cout. tie(0); cin >> n; n-=2; if(n==-1){ cout<<1; return 0; } powermod(A, n); int q = A[0][0]; cout << q; }
After doing this, I suddenly realized, just make a table to see if you can continue to use the quick power
fuck i’m so smart
#include <bits/stdc++.h> #define int long long using namespace std; const int N=5, M=1<<N, mod=998244353; int n,m; bool st[M]; int A[M][M],tmp[M][M],res[M][M]; void MXMP(int a[][M], int b[][M]) { memset(tmp, 0, sizeof tmp);//tmp is used to store the multiplication result for (int i = 0; i < (1<<n); i ++ ) { for (int j = 0; j < (1<<n); j ++ ) { for (int k = 0; k < (1<<n); k ++ ) { tmp[i][j] = (tmp[i][j] + (a[i][k] * b[k][j]) % mod) % mod;//Remember to touch mod } } } for (int i = 0; i < (1<<n); i ++ ) { for (int j = 0; j < (1<<n); j ++ ) { a[i][j] = tmp[i][j];//Remember to assign tmp to a } } } void powermod(int A[][M], int x) { memset(res, 0, sizeof res);//res stores the result for (int i = 0; i < (1<<n); i ++ ) { for (int j = 0; j < (1<<n); j ++ ) { res[i][j] = A[i][j]; } } while (x) { if (x & amp; 1) MXMP(res, A);//x is an odd number, multiply A by res MXMP(A, A);//Multiply A itself x >>= 1;//x divided by two } for (int i = 0; i < (1<<n); i ++ ) {//assign the result to A for (int j = 0; j < (1<<n); j ++ ) { A[i][j] = res[i][j]; } } } signed main() { ios_base::sync_with_stdio(0); cin. tie(0), cout. tie(0); cin>>n>>m; if((n & amp;1) & amp; & amp;(m & amp;1)){//judging whether they are all odd numbers cout<<0; return 0; } memset(st,true,sizeof st);//Whether the record can be placed for(int i=0;i<(1<<n);i ++ ){ int cnt=0; for(int j=0;j<n;j++){ if((i>>j) & amp;1){ if(cnt & amp;1){ st[i]=false; break; } }else cnt++; } if(cnt & amp;1) st[i]=false; } memset(A,0,sizeof A); for(int j=0;j<(1<<n);j++ ){ for(int k=0;k<(1<<n);k ++ ){ if((j & amp;k)==0 & amp; & amp;st[j|k]){ A[j][k]=1; //Which state can the record be inherited from? } } } m-=1;//Because res is assigned by A, res*A will count one more time and subtract one powermod(A,m);//Matrix fast power cout<<A[0][0]; /*for(int i=0;i<(1<<n);i + + ){ for(int j=0;j<(1<<n);j++ ){ cout<<A[i][j]<<' '; } cout<<'\\ '; }*/ \t }