1 条题解

  • 0
    @ 2026-7-4 11:29:10

    #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

    [AGC003F] Fraction of Fractal(重复loj6237)

    信息

    ID
    11522
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者