列表

详情

NC222484. USACOOpen20P]Sprinklers2:

描述

Farmer John has a small field in the shape of an N by N grid (1≤N≤2000) where the j-th square from the left of the i-th row from the top is denoted by (i,j) for all 1≤i,j≤N. He is interested in planting sweet corn and alfalfa in his field. To do so, he needs to install some special sprinklers.
A sweet corn sprinkler in square (I,J) will sprinkle all squares to the bottom-left: i.e. (i,j) with I≤i and j≤J.

An alfalfa sprinkler in square (I,J) will sprinkle all squares to the top-right: i.e. (i,j) with i≤I and J≤j.

A square sprinkled by one or multiple sweet corn sprinklers can grow sweet corn; a square sprinkled by one or multiple alfalfa sprinklers can grow alfalfa. But a square sprinkled by both types of sprinklers (or neither type) can grow nothing.

Help FJ determine the number of ways (modulo 109+7) to install sprinklers in his field, at most one per square, so that every square is fertile (i.e., sprinkled by exactly one type of sprinkler).

Some of the squares are already occupied by woolly cows; this doesn't prevent these squares from being fertile, but no sprinklers can be installed in such squares.

输入描述

The first line contains a single integer N.
For each 1≤i≤N, the i+1-st line contains a string of length N denoting the i-th row of the grid. Each character of the string is one of 'W' (indicating a square occupied by a woolly cow), or '.' (unoccupied).

输出描述

Output the remainder when the number of ways to install sprinklers is divided by 109+7.

示例1

输入: 

2
..
..

输出: 

28

说明:

Here are all fourteen possibilities when sweet corn can grow at (1,1).

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C  
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

示例2

输入: 

4
..W.
..WW
WW..
...W

输出: 

2304

说明:

This satisfies the constraints for the first subtask described below.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 171ms, 内存消耗: 67112K, 提交时间: 2021-08-31 13:06:09 

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n;
char s[2005][2005];
int dp[2005][2005][2],pre[2005][2005],suf[2005][2005];
int S[2005],ans;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1),reverse(s[i]+1,s[i]+n+1);
	for(int i=1;i<=n;i++){
		pre[i][0]=1;
		for(int j=1;j<=n;j++){
			pre[i][j]=pre[i][j-1];
			if(s[i][j]=='.') pre[i][j]=2*pre[i][j]%mod;
		}
		suf[i][n+1]=1;
		for(int j=n;j>=1;j--){
			suf[i][j]=suf[i][j+1];
			if(s[i][j]=='.') suf[i][j]=2*suf[i][j]%mod;
		} 
	}
	for(int i=0;i<=n;i++){
		if(s[1][i+1]=='.'||i==n) dp[1][i][0]=1ll*pre[1][i]*suf[1][min(i+2,n+1)]%mod;
		if((s[1][i+1]=='.'||i==n)&&(s[1][i]=='.'||i==0)) dp[1][i][1]=1ll*pre[1][max(0,i-1)]*suf[1][min(i+2,n+1)]%mod;
	}
	S[n+1]=dp[1][n+1][1];
	for(int i=n;i>=1;i--) S[i]=(S[i+1]+dp[1][i][1])%mod;
	for(int i=2;i<=n;i++){
		for(int j=0;j<=n;j++){
			(dp[i][j][0]+=1ll*dp[i-1][j][0]*pre[i][n]%mod)%=mod;
			if(s[i][j+1]=='.'&&j<n) (dp[i][j][0]+=1ll*S[j+1]*pre[i][j]%mod*suf[i][j+2]%mod)%=mod;
			if(s[i][j]=='.'&&j>0) (dp[i][j][1]+=1ll*dp[i-1][j][0]*pre[i][j-1]%mod*suf[i][j+1]%mod)%=mod;
			if(s[i][j]=='.'&&s[i][j+1]=='.'&&j<n&&j>0) (dp[i][j][1]+=1ll*S[j+1]*pre[i][j-1]%mod*suf[i][j+2]%mod)%=mod;
		}
		S[n+1]=dp[i][n+1][1];
		for(int j=n;j>=1;j--) S[j]=(S[j+1]+dp[i][j][1])%mod;
	}
	ans=dp[n][0][0];
	for(int i=1;i<=n;i++) (ans+=dp[n][i][1])%=mod;
	printf("%d\n",ans);

	return 0;
}

上一题

© 2025 nowcoder.com