传送门

又没看清楚题目。。。做的时候一直在想不连通怎么做,结果又读了遍题发现连通是条件。。。

钦定连通就好做啦,首先判判顶边和底边接在一起有没有黑格会变成相邻(即是否存在$i$使得$a_{1,i}=a_{n,i}=1$),有的话就记$s_1=1$,否则$s_1=0$,同时也判一下左右接在一起会不会有相邻,记为$s_2$。如果$s_1=s_2=1$,答案显然为$1$,直接判掉就行了。

不妨设$s_1=0,s_2=1$(反过来也一样),则把两个分形上下接在一起是没什么影响的(不会造成总联通块数减少),但左右接的话可能会导致有连通块合在一起,从而减小总连通块数。我们把一个$1$阶分形视为一个单位,则相邻两行之间就是独立的了。

我们记$a_k$为$1$个$k$阶分形的连通块个数,$b_k$为一个$k$阶分形的"两端都为$1$"的行数。则我们有转移$a_{k+1}=c_1a_k-c_2b_k,b_{k+1}=c_3b_k$,其中$c_1$为一个$1$阶分形的黑格子数,$c_2$为一次拼接过程中左右拼接的次数,$c_3$为一个$1$阶分形中"两端都为$1$"的行数。于是我们用矩阵快速幂加速一下这个转移就做完啦。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1010
#define LL long long
using namespace std;

const LL P=1000000007;

int n,m;
LL k;
int a[MAXN][MAXN];
LL c1,c2,c3;

struct Mat{
    struct Data{
        LL a[2][2];
    }*data;

    void alloc(){
        data=new Data; 
        memset(data->a,0,sizeof data->a);
    }

    void free(){ delete data; }

    LL& operator()(int i,int j){ return data->a[i][j]; }

    Mat clone(){
        Mat res;
        res.alloc();
        for(int i=0;i<2;i++) for(int j=0;j<2;j++) res(i,j)=data->a[i][j];
        return res;
    }
};

void mul(Mat x,Mat y){
    static LL temp[2][2];
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            temp[i][j]=(x(i,0)*y(0,j)+x(i,1)*y(1,j))%P;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            x(i,j)=temp[i][j];
}

Mat getPow(Mat x,LL y){
    Mat res;
    res.alloc();
    x=x.clone();
    for(int i=0;i<2;i++) res(i,i)=1;
    while(y){
        if(y&1) mul(res,x);
        mul(x,x);
        y>>=1;
    }
    x.free();
    return res;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d%lld",&n,&m,&k);
    if(!k){
        puts("1");
        return 0;
    }
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)
            if(str[j]=='#') a[i][j]=1;
    }
    bool flag1=0,flag2=0;
    for(int i=1;i<=m;i++) if(a[1][i] && a[n][i]) flag1=1;
    for(int i=1;i<=n;i++) if(a[i][1] && a[i][m]) flag2=1;
    if(flag1 && flag2){
        puts("1");
        return 0;
    }
    if(flag1){
        swap(flag1,flag2);
        swap(n,m);
        for(int i=0;i<MAXN;i++)
            for(int j=0;j<i;j++)
                swap(a[i][j],a[j][i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]) c1++;
            if(a[i][j] && a[i][j+1]) c2++;
        }
        if(a[i][1] && a[i][m]) c3++;
    }
    Mat trans;
    trans.alloc();
    trans(0,0)=c1;
    trans(1,1)=c3;
    trans(1,0)=-c2;
    trans=getPow(trans,k-1);
    LL ans=trans(0,0)+(flag2?trans(1,0):0);
    ans=(ans%P+P)%P;
    printf("%lld\n",ans);
}