【Codeforces】2017ACM/ICPC广西邀请赛 D-Covering

题意：4*n的区域，放置1*2和2*1的地砖，有多少种方法。

题解：矩阵快速幂+状压dp，或者 BM杜教

首先状压dp，找到转移状态，注释的地方为无效状态，有效状态只有6种

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod=1000000007;
ll a[4000][20];
int main()
{
	a[1][0]=1;
	for(int i=2;i<20;i++)
	{
		a[i][0]=(a[i-1][0]+a[i-1][3]+a[i-1][15]+a[i-1][9]+a[i-1][12])%mod;
		//a[i][1]=(a[i-1][2]+a[i-1][14]+a[i-1][8])%mod;
		//a[i][2]=(a[i-1][1]+a[i-1][13])%mod;
		a[i][3]=(a[i-1][12]+a[i-1][0])%mod;
		//a[i][4]=(a[i-1][8]+a[i-1][11])%mod;
		//a[i][5]=(a[i-1][10])%mod;           
		a[i][6]=(a[i-1][9])%mod;
		//a[i][7]=(a[i-1][8])%mod;
		//a[i][8]=(a[i-1][1]+a[i-1][4]+a[i-1][7])%mod;
		a[i][9]=(a[i-1][0]+a[i-1][6])%mod;
		//a[i][10]=(a[i-1][5])%mod;
		//a[i][11]=(a[i-1][4])%mod;
		a[i][12]=(a[i-1][0]+a[i-1][3])%mod;
		//a[i][13]=(a[i-1][2])%mod;
		//a[i][14]=(a[i-1][1])%mod;
		a[i][15]=(a[i-1][0])%mod;
		//if(a[i][0]==81898764)	cout<<666<<endl;
		cout<<a[i][0]<<endl;
	}
	return 0;
}

然后矩阵快速幂

#include<bits/stdc++.h>
#define N 6  	//确定矩阵大小 
#define MOD 1000000007   	//取模 
typedef long long int ll;
using namespace std;
ll res[N][N];	//存放结果的数组 
ll tmp[N][N];	//存放过程的数组 
ll init[N][N];	//初始系数矩阵 
int m;			//矩阵大小 
void multi(ll a[][N],ll b[][N])	//矩阵相乘 
{
	memset(tmp,0,sizeof(tmp));  
    for(int i=0;i<m;i++)  
    for(int j=0;j<m;j++)  
    for(int k=0;k<m;k++)  
    {  
        tmp[i][j]=((a[i][k]*b[k][j])%MOD+tmp[i][j])%MOD;  
        //a[i][j]=((a[i][k]*b[k][j])%MOD+a[i][j])%MOD; 
    } 
	for(int i=0;i<m;i++)  
    for(int j=0;j<m;j++)  
    {  
        a[i][j]=tmp[i][j];  
    }
	
}

void pow(ll a[][N],ll n)		//快速幂 
{
	memset(res,0,sizeof(res));
	for(int i=0;i<m;i++) res[i][i]=1;  //单位矩阵 
	while(n)
	{
		if(n&1)
		{
			multi(res,a);
		}
		multi(a,a);
		n>>=1;
	}
}

int main()
{
	m=6;
	ll n;
	while(cin>>n)
	{
		memset(res,0,sizeof(res));
		memset(tmp,0,sizeof(tmp));
		memset(init,0,sizeof(init));
		init[0][0]=1;
		init[0][1]=1;
		init[0][3]=1;
		init[0][4]=1;
		init[0][5]=1;
		init[1][0]=1;
		init[1][4]=1;
		init[2][3]=1;
		init[3][0]=1;
		init[3][2]=1;
		init[4][0]=1;
		init[4][1]=1;
		init[5][0]=1;
		pow(init,n);
		
		cout<<res[0][0]<<endl;
	}
	
	return 0;
} 

使用BM杜教也可以

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
const ll mod = 1000000007;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
// head

ll _, n;
namespace linear_seq {
	const int N = 10010;
	ll res[N], base[N], _c[N], _md[N];

	vector<int> Md;
	void mul(ll *a, ll *b, int k) {
		rep(i, 0, k + k) _c[i] = 0;
		rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
		for (int i = k + k - 1; i >= k; i--) if (_c[i])
			rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
		rep(i, 0, k) a[i] = _c[i];
	}
	int solve(ll n, VI a, VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
		ll ans = 0, pnt = 0;
		int k = SZ(a);
		assert(SZ(a) == SZ(b));
		rep(i, 0, k) _md[k - 1 - i] = -a[i]; _md[k] = 1;
		Md.clear();
		rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
		rep(i, 0, k) res[i] = base[i] = 0;
		res[0] = 1;
		while ((1ll << pnt) <= n) pnt++;
		for (int p = pnt; p >= 0; p--) {
			mul(res, res, k);
			if ((n >> p) & 1) {
				for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i]; res[0] = 0;
				rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
			}
		}
		rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
		if (ans < 0) ans += mod;
		return ans;
	}
	VI BM(VI s) {
		VI C(1, 1), B(1, 1);
		int L = 0, m = 1, b = 1;
		rep(n, 0, SZ(s)) {
			ll d = 0;
			rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
			if (d == 0) ++m;
			else if (2 * L <= n) {
				VI T = C;
				ll c = mod - d * powmod(b, mod - 2) % mod;
				while (SZ(C) < SZ(B) + m) C.pb(0);
				rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
				L = n + 1 - L; B = T; b = d; m = 1;
			}
			else {
				ll c = mod - d * powmod(b, mod - 2) % mod;
				while (SZ(C) < SZ(B) + m) C.pb(0);
				rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
				++m;
			}
		}
		return C;
	}
	int gao(VI a, ll n) {
		VI c = BM(a);
		c.erase(c.begin());
		rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
		return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
	}
};

int main() {
	while (~scanf("%lld", &n)) {
		vector<int>v;
		v.push_back(1);//前几项
		v.push_back(5);
		v.push_back(11);
		v.push_back(36);
		v.push_back(95);
		v.push_back(281);
		v.push_back(781);
		v.push_back(2245);
		//输入n ,输出第n项的值

		printf("%d\n", linear_seq::gao(v, n - 1));
	}
}