题解 AT2006 【Fraction of Fractal】
CYJian
·
·
题解
AGC003F
这题。。一开始没看到「保证黑格四连通」，自闭了很久。。
然后发现有这个条件之后好办很多了。
首先有了这个条件，我们就可以分三种情况讨论：
- 这个东西上下拼接、左右拼接都可以拼成一个联通块：显然答案是 1
- 这个东西上下拼接、左右拼接都不可以拼成一个联通块：显然答案是 c^{k-1}，其中 c 为图中黑点个数。
- 这个东西 上下拼接 或者 左右拼接 能拼成一个联通块（仅满足一个条件）：
这里问题就稍稍复杂一些了。
首先发现两个问题是等价的，所以这里只讨论左右拼接联通的情况：
我们先观察样例一的二级分形图：（已经手动分块）
容易发现，联通块个数可以简单的表示为：原图的 黑点个数 - 左右相邻两个都是黑格的对数。
然后我们把这个图当成原图，再放入一开始给出的图中，得到的新图的联通块个数也可以用上面这个表达式表示！
然后我们就发现，答案就是：k-1 级分形图中 黑点的个数 - 左右相邻两个都是黑格的对数。
黑点的个数很好求，就是 c^{k-1}。但是 相邻两个都是黑点的对数 比较难求。
我们考虑继续观察上图，不难发现，在每个块里头，都会有原图的 相邻黑点对数 的贡献。然后在边界上也会多出一些贡献。多出来的贡献恰好是 相邻黑点对数 \times 左右拼接边界上相邻黑点对数。
然后这样子我们就可以得到新图的 相邻黑点对数 了。
但是现在又多了一个麻烦：左右拼接边界上的相邻黑点对数怎么算？
我们发现，只有可能在原来 左右拼接边界相邻的行 代表的一串图的边界才可能有贡献。所以这个点对数就等于原图的这个点对数的平方。
如果我们设 a 为 相邻黑点对数， b 为 左右拼接边界相邻的黑点对数，c 为黑格数，那么上面的关系恰好可以写成矩阵连乘的形式：
\begin{bmatrix} c & a\\ 0 & b \end{bmatrix}^{k-1}
然后写个矩阵快速幂就好了。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;
#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)
template<typename T>
inline void read(T &x) {
char ch, t = 0; x = 0;
while(!isdigit(ch = ge)) t |= ch == '-';
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }
template<typename T>
inline void chkmin(T&a, T b) { a = a < b ? a : b; }
const int mod = 1e9 + 7;
int s[1010][1010];
struct Node {
int a, b, c;
Node() {}
Node(int a, int b, int c):a(a), b(b), c(c) {}
friend Node operator * (Node a, Node b) {
Node c;
c.a = 1LL * a.a * b.a % mod;
c.b = (1LL * a.a * b.b + 1LL * a.b * b.c) % mod;
c.c = 1LL * a.c * b.c % mod;
return c;
}
};
inline Node ksm(Node a, ll k) {
Node s(1, 0, 1);
while(k) {
if(k & 1) s = s * a;
a = a * a, k >>= 1;
} return s;
}
inline int fsp(int x, ll k) {
int s = 1;
while(k) {
if(k & 1) s = 1LL * s * x % mod;
x = 1LL * x * x % mod, k >>= 1;
}
return s;
}
int main() {
#ifdef LOCAL
FILE("");
#endif
int n = ri, m = ri; ll k = rl;
if(!k) return puts("1"), 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
char c = ge;
while(c != '.' && c != '#') c = ge;
s[i][j] = c == '#';
}
int ud = 0, lr = 0, c = 0, UD = 0, LR = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
c += s[i][j];
if(i == 1) UD += s[1][j] && s[n][j];
else ud += s[i][j] && s[i - 1][j];
if(j == 1) LR += s[i][1] && s[i][m];
else lr += s[i][j] && s[i][j - 1];
}
if(!UD && !LR) printf("%d\n", fsp(c, k - 1));
else if(UD && LR) puts("1");
else {
Node f;
if(UD) f = ksm(Node(c, ud, UD), k - 1);
else f = ksm(Node(c, lr, LR), k - 1);
printf("%d\n", (f.a - f.b + mod) % mod);
}
return 0;
}
```
upd: 感谢 M_sea 神仙提出一点小问题，已修改