Description

　　

​　　

　　

​　　

　　

Solution

　　

​　　 神题。

　　

​　　 定义一个上边界或下边界的格子为”上下接口“，当且仅当上下边界该位置的格子都是黑色的。

　　

​　　 ”左右接口“同理。

　　

　　首先特判掉\(k\)小于等于1的情况，答案都是1。

　　

​　　 然后特判掉两种情况：上下接口和左右接口同时存在时，答案显然为1；二者皆不存在时，答案就是\(s^{k-1}\)，其中\(s\)为给定网格的黑格子数目。

　　

​　　 所以接下来我们考虑的问题是：\(k\ge 2\)，且仅存在上下接口或左右接口。现在我们只考虑前者的情况，后者可以通过旋转原网格来达到同样的效果。

　　

​　　 首先来观察2级分形的结构：我们不妨把其中的每一块1级分形看做一个节点，如果两个相邻1级分形可以互相连通，则视为将其对应节点之间连一条边。由此我们对2级分形构造出一张图。

　　

​　　 对于3级及其以上分形，节点与边的定义不再扩展，依然是1级分形、表示1级分形之间是否连通。

　　

​　　 可以发现，由于当前只存在上下接口，因此2级分形的图是由若干条竖直方向的链构成的。推广一下，就会发现，对于\(k\)级分形\((k \ge 2)\)对应的图，它们都有着这个性质。

　　

​　　 将链看成树，我们就可以运用森林的性质：树的个数等于总点数减去总边数。则连通块个数等于总点数减去总边数。

　　

​　　 记\(a\)表示给定网格样式中，上下两个格子都是黑色的位置有多少，即\(\sum [map_{i,j}=map_{i+1,j}='\#']\)

　　

​　　 记\(b\)表示上下接口的个数（同一列的两个接口只算1个）

　　

​　　 记\(V_k\)表示\(k\)级分形图中点的个数，\(E_k\)表示\(k\)级分形图中边的条数。则有递推式：

　　

　　　　\(V_2=s\)，\(E_2=a\)

　　　　\(V_k=V_{k-1}*s\)，\(E_k=E_{k-1}*s+ab^{k-2}\)

　　　　

　　其中\(V\)的递推显然，而\(E\)的含义则是：每个低级分形中边个数乘上扩增倍数，加上低级分形在组合成高级分形时通过上下接口新产生的边数。注意\(b\)之所以含有一个幂形式，是因为随着分形级数的不断扩增，上下接口的数量也在不断增长。

　　

　　使用矩阵快速幂计算就做完了。

　　

　　

　　

Code

　　

#include 
    
     #include 
     
      using namespace std;typedef long long ll;const int N=1005;const int MOD=1e9+7;int n,m,blacksum;ll kk;char str[N][N];int map[N][N];int hcnt,vcnt,lh,lv;inline void plus(int &x,int y){    x=(x+y>=MOD)?(x+y-MOD):x+y;}inline void swap(int &x,int &y){    x^=y^=x^=y;}inline int fmi(int x,ll y){    int res=1;    for(;y;x=1LL*x*x%MOD,y>>=1)        if(y&1)            res=1LL*res*x%MOD;    return res;}struct Mat{/*{
    {
    {*/    int n,m;    int a[4][4];    Mat(){        memset(a,0,sizeof a);       }    Mat(int _n,int _m){        n=_n; m=_m;        clear();    }    void setUnit(){        if(n!=m) return;        for(int i=1;i<=n;i++)            a[i][i]=1;    }    void clear(){        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)                a[i][j]=0;    }    friend Mat operator * (Mat u,Mat v){        Mat res=Mat(u.n,v.m);        for(int i=1;i<=u.n;i++)            for(int j=1;j<=v.m;j++)                for(int k=1;k<=u.m;k++)                    //(res.a[i][j]+=1LL*u.a[i][k]*v.a[k][j]%MOD)%=MOD;                    plus(res.a[i][j],1LL*u.a[i][k]*v.a[k][j]%MOD);        return res;    }}O,T;/*}}}*/void readData(){    scanf("%d%d%lld",&n,&m,&kk);    for(int i=1;i<=n;i++){        scanf("%s",str[i]+1);        for(int j=1;j<=m;j++)            blacksum+=(str[i][j]=='#');    }}int getTypeAndInit(){    for(int i=1;i<=n;i++)        hcnt+=(str[i][1]=='#'&&str[i][m]=='#');    for(int j=1;j<=m;j++)        vcnt+=(str[1][j]=='#'&&str[n][j]=='#');    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){            if(j
      
       >=1)        if(y&1)            res=res*x;    return res;}void solve(){    fillMatrix();    T=mat_fmi(T,kk-2);    O=O*T;    int ans=O.a[1][1]-O.a[1][2];    printf("%d\n",ans<0?ans+MOD:ans);}int main(){    readData();     if(kk<=1){        puts("1");        return 0;    }    int type=getTypeAndInit();    if(type==1)//whole        puts("1");    else if(type==2)//isolated        printf("%d\n",kk==0?1:fmi(blacksum,kk-1));    else        solve();    return 0;}
      
     
    

​

​