1 条题解
-
0

#include <cstdio> #include <iostream> using namespace std; const int M = 1005; const int MOD = 1e9+7; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,k,cnt,tot[2],us[2];char s[M][M]; struct Mat { int a[2][2]; Mat() {a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;} Mat operator * (const Mat &b) const { Mat r; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) r.a[i][k]=(r.a[i][k]+a[i][j]*b.a[j][k])%MOD; return r; } }A; Mat qkpow(Mat a,int b) { Mat r; for(int i=0;i<2;i++) r.a[i][i]=1; while(b>0) { if(b&1) r=r*a; a=a*a; b>>=1; } return r; } int zxy(int a,int b) { int r=1; while(b>0) { if(b&1) r=r*a%MOD; a=a*a%MOD; b>>=1; } return r; } signed main() { n=read();m=read();k=read(); for(int i=1;i<=n;i++) { scanf("%s",s[i]+1); for(int j=1;j<=m;j++) if(s[i][j]=='#') { cnt++; if(j>1) tot[0]+=(s[i][j]==s[i][j-1]); if(i>1) tot[1]+=(s[i][j]==s[i-1][j]); } } for(int i=1;i<=n;i++) us[0]+=(s[i][1]=='#' && s[i][m]=='#'); for(int i=1;i<=m;i++) us[1]+=(s[1][i]=='#' && s[n][i]=='#'); if(us[0] && us[1]) {puts("1");return 0;} if(!us[0] && !us[1]) {printf("%d\n",zxy(cnt,k-1));return 0;} int z=us[0]?0:1; A.a[0][0]=cnt;A.a[0][1]=-tot[z];A.a[1][1]=us[z]; A=qkpow(A,k-1); printf("%lld\n",(A.a[0][0]+A.a[0][1]+MOD)%MOD); }
- 1
信息
- ID
- 8793
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者