WA on #2~4 #6,7 求条,50 pts
查看原帖
WA on #2~4 #6,7 求条,50 pts
926886
kind_aunt楼主2024/9/16 12:04
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e2+5;
const long long mod=1e9+7;
int n,m;
char s[N][N];
int X[N][N],sum[N][N];
int dp[N][N][N];
int ans=1;
int Mod(int x)
{
	return ((x+mod)%mod+mod)%mod;
}
void init()
{
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j++)
		{
			if(X[n][j]-X[n][i-1]){dp[n][i][j]=0;continue;}
			dp[n][i][j]=1;
			ans++;
			ans=Mod(ans);
		}
	return;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
			X[i][j]=X[i][j-1];
			if(s[i][j]=='X')
				X[i][j]++;
		}
	init();
	for(int k=n-1;k>=1;k--)
	{
		//前缀和
		for(int i=1;i<=m;i++)
			for(int j=i;j<=m;j++)
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[k+1][i][j],sum[i][j]=Mod(sum[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=i;j<=m;j++)
			{
				if(X[k][j]-X[k][i-1]) {dp[k][i][j]=0;continue;}
				dp[k][i][j]=sum[i][m]-sum[i][j-1];
				dp[k][i][j]=Mod(dp[k][i][j]);
				ans+=dp[k][i][j];
				ans=Mod(ans);
			}
	}
	cout<<ans<<'\n';
	return 0;
}
2024/9/16 12:04
加载中...