P7969 - Sprinklers 2: Return of the Alfalfa

内存限制：256 MB 时间限制：2 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：5 通过：3

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 ii-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 will sprinkle all squares to the bottom-left: i.e. with and j≤J.

An alfalfa sprinkler in square will sprinkle all squares to the top-right: i.e. with and .

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 ) 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.

INPUT FORMAT (file sprinklers2.in):

The first line contains a single integer N.N. For each 1≤i≤N,1≤i≤N, the i+1i+1-st line contains a string of length NN denoting the ii-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 FORMAT (file sprinklers2.out):

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

SAMPLE INPUT:

2
..
..

SAMPLE OUTPUT:

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., .., ..

SAMPLE INPUT:

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

SAMPLE OUTPUT:

This satisfies the constraints for the first subtask described below.

SCORING:

Test cases 3-4 satisfy N≤10 and there are at most ten unoccupied squares.
Test cases 5-9 satisfy N≤200.
Test cases 10-16 satisfy no additional constraints.

USACO 2020 US Open Contest, Platinum

7969: Sprinklers 2: Return of the Alfalfa

题目描述

INPUT FORMAT (file sprinklers2.in):

OUTPUT FORMAT (file sprinklers2.out):

SAMPLE INPUT:

SAMPLE OUTPUT:

SAMPLE INPUT:

SAMPLE OUTPUT:

SCORING:

输入样例复制

输出样例复制

分类标签

7969: Sprinklers 2: Return of the Alfalfa

题目描述

INPUT FORMAT (file sprinklers2.in):

OUTPUT FORMAT (file sprinklers2.out):

SAMPLE INPUT:

SAMPLE OUTPUT:

SAMPLE INPUT:

SAMPLE OUTPUT:

SCORING:

输入样例 复制

输出样例 复制

分类标签

输入样例复制

输出样例复制