【矩阵加速】AGC003 Fraction of Fractal

分析：

想了半天才看见给的图是联通的。。。。

那就很简单了，设ud表示：上界和下界相同位置都为’#‘的数量。lr表示：左界和右界相同的位置都为‘#’的数量。
设$v$表示’#‘的数量，$ev$表示左右相邻都是’#‘的数量，$eh$表示上下相邻都是’#'的数量。

显然，如果$lr>0且ud>0$，那无论怎么扩展，都一定联通，答案为1。
如果$lr=0且ud=0$，那么无论怎么扩展，扩展后一定都不联通，答案就是$v^{k?1}$
考虑$lr，ud$有一个为0的情况。显然，哪个是0哪个不是并不重要。因为可以翻转这个图，使得$lr,ud$交换（记得同时要交换eh,ev）

现在只讨论ud=0的情况。

显然，这种情况下，如果把每个1次扩展图看作一个点，连起来的图一定没有环（因为边都是上下方向的）。

那么联通块数量=点数量$(V)$-边数量$(E)$

那么有个很显然的递推式：
$V_k=V_{k?1}?v$
$E_k=lr?E_{k?1}+ev?V_{k?1}$
上面那个很显然，就不解释了。
下面那个可以分为两部分，前半部分求的是两个图之间的边，后半部分是一个图内部的边。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
#define MOD 1000000007
using namespace std;
typedef long long ll;
char s[MAXN][MAXN];
int n,m,v,lr,ud,ev,eh;
ll k;
struct node{
    ll x[3][3];node operator *=(const node&t) {
    int c[3][3]={
    0};for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int l=1;l<=2;l++)c[i][j]+=(x[i][l]*t.x[l][j])%MOD;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)x[i][j]=c[i][j]%MOD;}
}e,a;
ll fsp(ll x,ll y){
    ll res=1;while(y){
    if(y&1ll)res=res*x%MOD;x=x*x%MOD;y>>=1ll;	}return res;
}
int main(){
    SF("%d%d%lld",&n,&m,&k);for(int i=1;i<=n;i++)SF("%s",s[i]+1);for(int i=1;i<=m;i++)if(s[1][i]=='#'&&s[n][i]=='#')ud++;for(int i=1;i<=n;i++)if(s[i][1]=='#'&&s[i][m]=='#')lr++;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    if(s[i][j]=='#'){
    v++;if(s[i-1][j]=='#')ev++;if(s[i][j-1]=='#')eh++;	}}if(ud!=0&&lr!=0){
    PF("1");return 0;}if(ud==0&&lr==0){
    PF("%lld",fsp(v,k-1ll));	return 0;}if(ud==0){
    ud=lr;ev=eh;}e.x[1][1]=ud;e.x[2][1]=ev;e.x[1][2]=0;e.x[2][2]=v;a.x[1][2]=1;if(k==0){
    PF("1\n");return 0;	}k--;while(k){
    if(k&1ll)a*=e;e*=e;k>>=1ll;}PF("%lld",(a.x[1][2]-a.x[1][1]+MOD)%MOD);
}