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

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

Farmer John has a small field in the shape of an NN by NN grid (1≤N≤20001≤N≤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≤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)(I,J) will sprinkle all squares to the bottom-left: i.e. (i,j)(i,j) with I≤iI≤i and j≤Jj≤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≤I and J≤jJ≤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+7109+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.

 

 

 

SAMPLE INPUT:

2
..
..

SAMPLE OUTPUT:

28

Here are all fourteen possibilities when sweet corn can grow at (1,1)(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:

2304

This satisfies the constraints for the first subtask described below.

 

 

Problem credits: Benjamin Qi

USACO 2020 US Open Contest, Platinum Problem 1. Sprinklers 2: Return of the Alfalfa Return to Problem List 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Suppose that sweet corn grows in (1,1)(1,1). Consider the minimum jj such that alfalfa grows in (1,j)(1,j).

 

• Sweet corn grows in (1,y)(1,y) if y<jy<j and alfalfa grows in (1,y)(1,y) otherwise.
• Every square (x,y)(x,y) satisfying y<jy<j contains either a sweet corn sprinkler or no sprinkler.
• There must be a sweet corn sprinkler at (1,j−1)(1,j−1).

Now,

• If j=N+1j=N+1 then sweet corn grows in every square.
• Otherwise, run the solution recursively on the remaining N×(N+1−j)N×(N+1−j) sub-rectangle; namely, those squares (x,y)(x,y) such that y≥jy≥j. Find the minimum kk such that sweet corn grows in (k,j)(k,j), and continue in a similar fashion.

In general, an assignment of sweet corn or alfalfa to each square corresponds to a down-right path from (1,1)(1,1) to some square (x,y)(x,y) that satisfies x=N+1x=N+1 or y=N+1y=N+1. In the above example, the first three squares of the path are (1,1)→(1,j)→(k,j)(1,1)→(1,j)→(k,j). The squares that are just before where the path changes direction (such as (1,j−1)(1,j−1)) must contain a sprinkler of a certain type (so their states are fixed), while every other square that does not contain a cow can be in one of two states: either place no sprinkler or place a sprinkler of the same type as the crop that grows in that square. A path that changes direction dd times fixes the states of d+1d+1 squares, so the states of the remaining squares can be assigned in 2(# unoccupied squares)−d−12(# unoccupied squares)−d−1 ways. It suffices to sum 2−d−12−d−1 over all paths and then multiply the answer by 2(# unoccupied squares)2(# unoccupied squares) at the end. In the code below, p≡2−1(mod109+7)p≡2−1(mod109+7).

We can do this naively in O(N3)O(N3) and use prefix sums to get O(N2)O(N2). It is probably easier to write the O(N3)O(N3) solution first and then figure out how to optimize it.

Dhruv Rohatgi's code:

 

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define MOD 1000000007
 
int N;
long long p = 500000004LL;
char A[2005][2005];
char B[2005][2005];
int r[2005][2005];
int b[2005][2005];
int psr[2005][2005];
int psb[2005][2005];
 
int main()
{
	freopen("sprinklers2.in","r",stdin);
	freopen("sprinklers2.out","w",stdout);
	cin >> N;
	for(int i=0;i<N;i++)
		cin >> (A[i+1]+1);
	for(int i=2;i<=N+1;i++)
		if(A[i-1][1] == '.')
			b[i][0] = psb[i][0] = p;
	for(int j=1;j<=N;j++)
		if(A[1][j] == '.')
			r[1][j] = psr[1][j] = p;
	for(int i=2;i<=N+1;i++)
		for(int j=1;j<=N;j++)
		{
			if(A[i][j] == '.')
			{
				r[i][j] = (p*psb[i][j-1])%MOD;
			}
			if(A[i-1][j+1] == '.')
			{
				b[i][j] = (p*psr[i-1][j])%MOD;
			}
			psr[i][j] = (psr[i-1][j] + r[i][j])%MOD;
			psb[i][j] = (psb[i][j-1] + b[i][j])%MOD;
		}
	int ans = (psr[N][N] + psb[N+1][N])%MOD;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			if(A[i][j]=='.')
				ans = (2LL*ans)%MOD;
	cout << ans << '\n';
}

[/hide]