hbcpc problem J domino game (like pressure dp+matrix fast power)

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
}