摘要:矩阵优化dp

luogu4910帕秋莉的手环

题面

题目分析

原题面狗屁不通,翻译一下:

求构造一个长度为n的01环,使得没有相邻的0的方案数.

于是可以写一个简单dp,设$f_{i,0/1}$为仅考虑前$i$位,这一位上放$0/1$的方案数.

转移:

构造矩阵表示整个转移过程:

于是可以用矩阵快速幂加速递推.

答案为$f_{n,1}+f_{n-1,0}$,因为考虑是一个环,最后一位和第一位同时放$0$的情况要除去.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl small=4,p=1000000007;
lxl T_,n;
struct _Matrix
{
lxl a[small][small];
_Matrix(){memset(a,0,sizeof a);}
inline lxl* operator [](const lxl &i){return a[i];}
inline _Matrix operator *(const _Matrix &another)const
{
_Matrix b;
R int i,j,k;
for(i=0;i<small;++i)
for(k=0;k<small;++k)
for(j=0;j<small;++j)
b.a[i][j]=(b.a[i][j]+a[i][k]*another.a[k][j]%p)%p;
return b;
}
}I,T,A;
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline _Matrix FastPow(_Matrix A,lxl b)
{
_Matrix C=I;
for(;b;b>>=1,A=A*A)if(b&1)C=C*A;
return C;
}
inline void prework()
{
T[0][0]=T[0][1]=1;
A[0][1]=A[0][2]=1;
A[1][0]=A[1][1]=A[1][3]=1;
for(R int i(0);i<small;++i)I[i][i]=1;
}
int main(void)
{
prework();
T_=read();
while(T_--)
{
n=read();
_Matrix B=T*FastPow(A,n-1);
printf("%lld\n",(B[0][1]+B[0][2])%p);
}
return 0;
}