浣熊的长木桥 题解
Su777
·
·
题解
本题解中，B,C,D,E 方块统称为 L 型方块。
m=0
这是经典的 2\times n 铺砖问题，采用线性递推。
设 f(x) 表示前 x 列的方案数，有初始值：
f(0)=1,f(1)=1,f(2)=5
递推关系为：
f(x)=f(x-1)+4f(x-2)+2f(x-3)
画图不难理解。使用矩阵快速幂即可在 O(\log n) 时间内完成，并且轻松通过特殊性质 A，获得 35 分。
m\neq 0
考虑上面递推式中的 7 种铺放情况：
- A 型方块：其所在位置是否已有已知方块不影响结果（等效）
- L 型方块：其覆盖的 3 个格子必须全部为空，否则不可用（不等效）
用一个 bool 数组记录每个格子是否被占用，在每一步递推时枚举并判断所有情况即可。
初始化细节
-
x=1$：对应测试点 #1，$f(1)=1
-
- $2\times2$ 全空：$f(2)=5
- 只占 1 个格子：f(2)=2
- 占用 \ge 2 个格子：f(2)=1
这时加上送分的特殊性质 A 可以获得 70 分。下面考虑正解怎么做。
正解
其实特殊性质 A 提示了要将状态转移进行分段。
在没有已知方块的连续区间中，递推始终是同一个线性递推，逐列模拟非常浪费。不如直接用矩阵快速幂整体推进。一个已知的方块只会影响它所在列及所在列右边两列的总共三次递推，这些列只能分类讨论一个一个推；而未被影响的 $O(m)$ 个递推区间，使用矩阵加速递推来做。
列号值域为 $[1,10^{18}]$，直接用数组存会 MLE，可以离散化。
### 验题人代码
```cpp
#include<bits/stdc++.h>
#define endl '\n'
using ll = long long;
using namespace std;
const int mod = 1e9 + 7;
ll n;
int m;
struct Matrix{
int a[4][4];
Matrix(){
memset(a, 0, sizeof(a));
}
int* operator [] (const int &x){return a[x];}
const int* operator [] (const int &x) const{return a[x];}
friend Matrix operator * (const Matrix &a, const Matrix &b){
Matrix res;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++)
res[i][k] = (res[i][k] + 1ll * a[i][j] * b[j][k]) % mod;
return res;
}
}tr;
map<ll, int> mp;
Matrix qpow(Matrix x, ll y){
Matrix res;
for (int i = 0; i < 4; i++) res[i][i] = 1;
while (y){
if (y & 1) res = res * x;
x = x * x;
y >>= 1;
}
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
tr[0][0] = 1;
tr[0][1] = 1;
tr[0][2] = 1;
tr[0][3] = 2;
tr[1][0] = 1;
tr[1][1] = 0;
tr[1][2] = 0;
tr[1][3] = 1;
tr[2][0] = 1;
tr[2][1] = 0;
tr[2][2] = 0;
tr[2][3] = 1;
tr[3][0] = 1;
cin >> n >> m;
while (m--){
ll x;
int y;
cin >> y >> x;
mp[x] |= 1 << (y - 1);
}
Matrix ans;
ans[0][0] = 1;
ll p = 1;
for (auto [x, y] : mp){
ans = ans * qpow(tr, x - p);
p = x;
if (y == 1){
int a = (ans[0][0] + ans[0][2]) % mod, b = ans[0][0];
memset(ans.a[0], 0, sizeof(ans.a[0]));
ans[0][0] = a, ans[0][3] = b;
}else if (y == 2){
int a = (ans[0][0] + ans[0][1]) % mod, b = ans[0][0];
memset(ans.a[0], 0, sizeof(ans.a[0]));
ans[0][0] = a, ans[0][3] = b;
}else{
int a = ans[0][0];
memset(ans.a[0], 0, sizeof(ans.a[0]));
ans[0][0] = a;
}
p++;
}
ans = ans * qpow(tr, n - p + 1);
cout << ans[0][0];
return 0;
}
```