poj3420 Quad Tiling--状压dp+矩阵快速幂

原题链接：​​http://poj.org/problem?id=3420​​

题意：一个4*n的格子，一个1*2的填充，求填充方式。

分析：n最大是10^9，比较大，用矩阵快速幂优化速度。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

typedef long long ll;
int MOD;

struct Mat
{
  ll at[16][16];

  Mat()
  {
    memset(at, 0, sizeof(at));
  }

  friend Mat operator*(Mat& mat1, Mat& mat2)
  {
    Mat re;
    for (int i = 0; i < 16; i++)
    {
      for (int k = 0; k < 16; k++)
      {
        if (mat1.at[i][k] == 0)
          continue;
        for (int j = 0; j < 16; j++)
        {
          re.at[i][j] += (mat1.at[i][k] * mat2.at[k][j]);
          re.at[i][j] %= MOD;
        }
      }
    }
    return re;
  }

  friend Mat operator^(Mat mat, int n)
  {
    if (n == 1)return mat;
    Mat re;
    for (int i = 0; i < 16; i++)
      re.at[i][i] = 1;

    while (n)
    {
      if (n & 1)
        re = re*mat;
      n = n >> 1;//注意要赋值给n，右移会返回一个新值，而不会修改原值
      mat = mat*mat;
    }

    return re;
  }
};

Mat m;

void dfs(int l, int now, int pre)
{
  if (l > 4)return;
  if (l == 4)
  {
    m.at[pre][now] = 1;
    return;
  }

  dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);//横
  dfs(l + 1, (now << 1) | 1, (pre << 1));//竖
  dfs(l + 1, (now << 1), (pre << 1) | 1);//不放
}

int main()
{
  int n;
  dfs(0, 0, 0);
  while (~scanf("%d %d", &n, &MOD))
  {
    if (n == 0 && MOD == 0)
      break;
    if (MOD == 1)//有点坑，当输入数据1 1 的时候不加这句就会错，其他数据都可以去掉这句代码
    {
      printf("0\n");
      continue;
    }
    Mat ans = m^n;
    printf("%lld\n", ans.at[15][15]);
  }
  return 0;
}