(mathcal{Description})
Link.
给定一个长度为 (n) 的木板，木板上有 (m) 个标记点，第 (i) 个标记点距离木板左端点的距离为 (x_i)，现在你需要在木板上放置一些不相交正方形，正方形需要满足：
-
正方形的边长为整数。
-
正方形底面需要紧贴木板。
-
正方形不能超出木板，正方形要将所有的木板覆盖。
-
标记点的位置不能是两个正方形的交界处。
求所有合法放置方案的正方形面积的乘积之和。对 (10^9+7) 取模。
(nle10^9)，(mle10^5)。
(mathcal{Solution})
嘛……有时候题意转换……就挺突然的 qwq。
你有 (n) 个空格排成一行，格子边缘可以放隔板，其中第一格左侧和最后一格右侧必须放，标记位置不能放。然后在每两块隔板间放两个不同色的小球，可以放同一个位置。求方案数。
不难证明与原问题等价。我们来考虑这个新问题。
令 (f(i,0/1/2)) 表示前 (i) 个位置放好球，其中最后一段区间已经放了 (0/1/2) 个球的方案数。转移：
- 不放隔板：
[egin{aligned}
f(i,0)&=f(i-1,0)\
f(i,1)&=f(i-1,1)+f(i-1,0)\
f(i,2)&=f(i-1,2)+2f(i-1,1)+f(i-1,0)
end{aligned}
]
- 放隔板：
[f(i,0/1/2)=f(i-1,2)
]
实际上只需要“随便放”和“不放”两种选择，把状态写成列向量 (egin{bmatrix}f(i,0)\f(i,1)\f(i,2)end{bmatrix})，构造两种转移矩阵：
- 不放：
[A=egin{bmatrix}
1&0&0\
2&1&0\
1&1&1
end{bmatrix}
]
- 随便放：
[B=egin{bmatrix}
2&1&1\
2&1&0\
1&1&1
end{bmatrix}
]
在相邻两个标记点之间矩阵快速幂加速 DP 即可。复杂度 (mathcal O(3^3mlog n))。
(mathcal{Code})
#include <cstdio>
#include <assert.h>
typedef long long LL;
const int MAXM = 1e5, MOD = 1e9 + 7;
int n, m;
inline int add ( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline int mul ( LL a, const int b ) { return ( a *= b ) < MOD ? a : a % MOD; }
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
struct Matrix {
int n, m, mat[3][3];
Matrix (): n ( 0 ), m ( 0 ), mat {} {}
Matrix ( const int tn, const int tm ): n ( tn ), m ( tm ), mat {} {}
inline int* operator [] ( const int key ) { return mat[key]; }
inline Matrix operator * ( Matrix t ) {
assert ( m == t.n );
Matrix ret ( n, t.m );
for ( int i = 0; i < n; ++ i ) {
for ( int k = 0; k < m; ++ k ) {
for ( int j = 0; j < t.m; ++ j ) {
ret[i][j] = add ( ret[i][j], mul ( mat[i][k], t[k][j] ) );
}
}
}
return ret;
}
};
inline Matrix qkpow ( Matrix a, int b ) {
Matrix ret ( a.n, a.m );
for ( int i = 0; i < ret.n; ++ i ) ret[i][i] = 1;
for ( ; b; a = a * a, b >>= 1 ) if ( b & 1 ) ret = ret * a;
return ret;
}
Matrix I ( 3, 1 ), A ( 3, 3 ), B ( 3, 3 );
inline void init () {
I[0][0] = 1;
A[0][0] = 1;
A[1][0] = 2, A[1][1] = 1;
A[2][0] = A[2][1] = A[2][2] = 1;
B = A, ++ B[0][0], ++ B[0][1], ++ B[0][2];
}
int main () {
init ();
n = rint (), m = rint ();
int las = 0;
for ( int i = 1, x; i <= m; ++ i ) {
x = rint ();
I = A * qkpow ( B, x - las - 1 ) * I;
las = x;
}
I = A * qkpow ( B, n - las - 1 ) * I;
printf ( "%d
", I[2][0] );
return 0;
}