模型转化题,转化不出来就白给。
可以把题目的条件翻译成以下组合语言:
- 有一排 \(n\) 个格子,你要在其中插入若干个隔板将其隔成若干段
- 有 \(m\) 个特殊格子 \(a_1,a_2,\dots,a_m\),\(\forall i\in [1,m]\) 你禁止在 \(a_i\) 与 \(a_{i}+1\) 之间放隔板
- 在相邻隔板之间的格子中需恰好放上两个不同的球(可以重合)
不难发现,上述题面中的”隔板“对应原题中的正方形边界,对于一段长度为 \(l\) 的段,在上面放两个不同的球的方案数为 \(l^2\),也就对应了原题面中的”平方“,而原题中的乘法在上述题面中被翻译成了乘法原理。因此我们就将这题与组合意义联系在了一起。
设 \(f_{i,j}\) 表示现在考虑了前 \(i\) 个位置,在当前位置到上一个隔板的区间中放上了 \(j\) 个球的方案数,其中 \(j\in [0,2]\)。
对于非特殊格子 \(i\) 我们有状态转移方程:
- \(f_{i+1,0}=f_{i,0}+f_{i,2}\)
- \(f_{i+1,1}=(2f_{i,0}+f_{i+1,1})+2f_{i,2}\)
- \(f_{i+1,2}=(f_{i,0}+f_{i,1}+f_{i,2})+f_{i,2}\)
注意这里将不放隔板的转移都放在了前面,放隔板的转移都放在了后面。
对于特殊格子的话状态转移方程只要把放隔板的转移去掉就行了。
不难发现这可以写成矩阵形式。
时间复杂度 \(\mathcal O(m\log n\omega^3)\),其中 \(\omega=3\)。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n, m;
struct mat {
int a[3][3];
mat (){}
void clear() { memset(a, 0, sizeof a); }
void init() { clear(); for (int i = 0; i < 3; ++i) a[i][i] = 1; }
mat operator * (const mat &x) const {
mat res; res.clear();
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * x.a[k][j] % mod) % mod;
return res;
}
} f, x, y;
mat qpow(mat x, int y) {
mat res; res.init();
while (y) {
if (y & 1) res = res * x;
x = x * x;
y >>= 1;
}
return res;
}
int main() {
f.a[0][0] = 1;
x.a[0][0] = 1, x.a[0][1] = 0, x.a[0][2] = 1;
x.a[1][0] = 2, x.a[1][1] = 1, x.a[1][2] = 2;
x.a[2][0] = 1, x.a[2][1] = 1, x.a[2][2] = 2;
y.a[0][0] = 1, y.a[0][1] = 0, y.a[0][2] = 0;
y.a[1][0] = 2, y.a[1][1] = 1, y.a[1][2] = 0;
y.a[2][0] = 1, y.a[2][1] = 1, y.a[2][2] = 1;
scanf("%d%d", &n, &m); int lst = -1;
for (int i = 1, cur; i <= m; ++i) {
scanf("%d", &cur);
f = qpow(x, cur - lst - 1) * f, f = y * f, lst = cur;
}
f = qpow(x, n - lst - 1) * f;
printf("%d", f.a[2][0]);
return 0;
}
标签:AGC013E,mat,格子,隔板,int,res,++
From: https://www.cnblogs.com/Kobe303/p/16849839.html