Submission #848237

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define SIZE 1005
#define MOD 1000000007

using namespace std;
typedef long long int ll;

ll mpow(ll m,ll t)
{
	if(t==0) return 1LL;
	ll ret=mpow(m,t/2);
	ret=ret*ret%MOD;
	if(t%2==1) ret=ret*m%MOD;
	return ret;
}
ll inv(ll x)
{
	return mpow(x,MOD-2);
}
char mp[SIZE][SIZE];

int main()
{
	int n,m;
	ll K;
	scanf("%d %d %lld",&n,&m,&K);
	bool A=false,B=false;
	for(int i=0;i<n;i++) scanf("%s",&mp[i]);
	ll S=0,T=0;
	for(int i=0;i<n;i++) if(mp[i][0]=='#'&&mp[i][m-1]=='#') A=true,S++;
	for(int i=0;i<m;i++) if(mp[0][i]=='#'&&mp[n-1][i]=='#') B=true,T++;
	if(A&&B) puts("1");
	else if(K<=1) puts("1");
	else
	{
		ll cnt=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(mp[i][j]=='#') cnt++;
			}
		}
		if(!A&&!B) printf("%lld\n",mpow(cnt,K-1));
		else
		{
			ll mn=0;
			if(A)
			{
				for(int i=0;i<n;i++)
				{
					for(int j=0;j+1<m;j++)
					{
						if(mp[i][j]=='#'&&mp[i][j+1]=='#') mn++;
					}
				}
				mn=mn%MOD;
			}
			else
			{
				S=T;
				for(int i=0;i+1<n;i++)
				{
					for(int j=0;j<m;j++)
					{
						if(mp[i][j]=='#'&&mp[i+1][j]=='#') mn++;
					}
				}
				mn=mn%MOD;
			}
			//f(K)=f(K-1)*cnt-mn*S^(K-2) , f(1)=1
			//printf("%lld %lld %lld\n",cnt,mn,S);
			cnt=cnt*inv(S)%MOD;
			mn=mn*inv(S*S)%MOD;
			ll ans;
			if(cnt==1) ans=inv(S)+(MOD-mn)*(K-1)%MOD;
			else
			{
				ll ap=mn*inv(cnt-1)%MOD;
				ans=mpow(cnt,K-1)*(inv(S)-ap+MOD)%MOD;
				ans+=ap;
				ans%=MOD;
			}
			ans=ans*mpow(S,K)%MOD;
			printf("%lld\n",ans);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:31:40: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[1005]’ [-Wformat=]
  for(int i=0;i<n;i++) scanf("%s",&mp[i]);
                                        ^
./Main.cpp:29:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld",&n,&m,&K);
                              ^
./Main.cpp:31:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%s",&mp[i]);
                                         ^

Judge Result