#PU1044. USACO 2020 US Open Contest, Platinum — Problem 1. Sprinklers 2: Return of the Alfalfa

    ID: 1609 传统题 文件IO:sprinklers2 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open20来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2020 US Open Contest, Platinum — Problem 1. Sprinklers 2: Return of the Alfalfa

USACO 2020 US Open Contest, Platinum — Problem 1. Sprinklers 2: Return of the Alfalfa

题目描述

Farmer John has a small field in the shape of an NN by NN grid (1≤N≤20001 \le N \le 2000) where the jj-th square from the left of the ii-th row from the top is denoted by (i,j)(i,j) for all 1≤i,j≤N1 \le i,j \le 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)(I,J) will sprinkle all squares to the bottom-left: i.e. (i,j)(i,j) with I≤iI \le i and j≤Jj \le J. An alfalfa sprinkler in square (I,J)(I,J) will sprinkle all squares to the top-right: i.e. (i,j)(i,j) with i≤Ii \le I and J≤jJ \le 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+710^9 + 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.N. For each 1≤i≤N,1\le i\le 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).

输出格式

(见题面原文)

数据范围

Test cases 3-4 satisfy N≤10N\le 10 and there are at most ten unoccupied squares. Test cases 5-9 satisfy N≤200N\le 200. Test cases 10-16 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 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.