Topcoder Single Round Match 639 DIv2 T3 BoardFoldingDiv2 题解

## Translation

• paper will contain between 1 and 50 elements, inclusive.
• Each element of paper will contain between 1 and 50 elements, inclusive.
• All elements of paper will have the same length.
• paper will contain only characters '0' and '1'.
• Time limit (s): 2.000
• Memory limit (MB): 256
• Stack limit (MB): 256

## Examples

{"10",
"11"}

Returns: 1

There is no valid way to fold this paper, so there is just one possible outcome.

{"1111111",
"1111111"}

Returns: 84

We can fold it into any of the 84 possible subrectangles of the original rectangle.

{"0110",
"1001",
"1001",
"0110"}

Returns: 9

## Original

Little Petya likes puzzles a lot. Recently he has received one as a gift from his mother. The puzzle has the form of a rectangular sheet of paper that is divided into N rows by M columns of unit square cells. Rows are numbered 0 through N-1 from top to bottom, and columns 0 through M-1 from left to right. Each cell is colored either black or white. You are given a description of the paper, the exact format is specified at the end of this problem statement. The goal of the puzzle is to fold the paper. This has to be done in a sequence of turns. In each turn, Petya has to fold the paper according to the rules below. He can end the process after any number of turns (including zero), even if there are still valid ways to fold the paper. In each turn, Petya must follow these steps: To start folding, he must choose a line that is parallel to one of the sides of the paper and passes between two rows/columns of cells. He can then take the smaller part of the paper and fold it on top of the larger part. (If the line divides the current paper in half, he can fold either half on top of the other.) There is one additional restriction: Petya may only perform the fold if all cells of the part that is being folded land on equally-colored cells of the part that remains in place. For example, consider the following paper (with 0 and 1 representing white and black):
10010101
11110100
00000000
01101110
Here, Petya could choose the vertical line that goes between the two leftmost columns and the rest of the paper. Note that this is a valid choice: as he makes the fold, the cells from the leftmost two columns will all match their counterparts in the right part of the paper. This is how the paper looks like after the fold (with periods representing empty spaces):
..010101
..110100
..000000
..101110
Clearly, even after multiple folds the paper will always look like a subrectangle of the original paper. Two states of the game are considered the same if that rectangle has the same dimensions and the same offset with respect to the original top left corner of the paper. (Note that folding order does not matter. Two different sequences of folding may produce the same final state.) You are given a description of the original state of the paper as a vector paper. Here N is the number of elements in paper and M is the length of its each element. For each i and j, the character paperi is either '0' (meaning that the cell (i,j) is white) or '1' (the cell is black). Compute and return the number of possible final states of the game.

## Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=55;
int n,m,ans1,ans2;
bool vis[maxn][maxn]; // vis[i][j]: 第i个cell开始的一段长度为j的闭区间能否与i+j+1开始的一段等长的闭区间匹配
// 即[i,i+j]与[i+j+1,i+2*j+1]两段区间的cells是否对称
// 注意j是整个区间半长
bool f[maxn][maxn]; // F[i][j]: 能否折叠得只剩[i,j]区间
class BoardFoldingDiv2 {
public:
int howMany( vector <string> paper );
};
inline bool Check(int x,int y,bool mode,vector <string> paper){ // 验证两行/两列是否相同的函数
// mode: 竖向验证(true)(||)或横向验证(false)(=)
if (mode){
for (int i=0;i<n;i++) if (paper[i][x]!=paper[i][y]) return false;
// printf("Check Succesful: %d %d\n",x,y);
return true;
} else {
for (int i=0;i<m;i++) if (paper[x][i]!=paper[y][i]) return false;
return true;
}
return false;
}
int BoardFoldingDiv2::howMany(vector <string> paper) {
n=paper.size();
if (n==0) return 0;
m=paper[0].length();

// Part 1: build ans1 -------------------------------

memset(vis,0,sizeof(vis));
for (int i=0;i<m-1;i++) vis[i][1]=Check(i,i+1,true,paper);
for (int L=3;L<=m;L+=2)
for (int i=0;i<m-L;i++){
int j=i+L;
if ((j>=m)||(!vis[i+1][L/2])) continue;
vis[i][(L+1)/2]=Check(i,j,true,paper);
}

memset(f,0,sizeof(f));
f[0][m-1]=true;
for (int L=m-1;L>=0;L--)
for (int i=0;i<m-L;i++){
int j=i+L;
if (j>=m) continue;
for (int k=i;(k<=j)&&(!f[i][j]);k++){
if ((j+(j-k+1)<m)&&(vis[k][j-k+1])){ // 先考虑右边一块向左边折叠情况
f[i][j]|=f[i][j+(j-k+1)];
}
if ((i-(k-i+1)>=0)&&(vis[i-(k-i+1)][k-i+1])){ // 左边一块向右折叠
f[i][j]|=f[i-(k-i+1)][j];
}
}
}
ans1=0;
for (int i=0;i<m;i++)
for (int j=i;j<m;j++) ans1+=f[i][j];
if (m==1) ans1=1;

// Part 2: build ans2 -------------------------------

memset(vis,0,sizeof(vis));
for (int i=0;i<n-1;i++) vis[i][1]=Check(i,i+1,false,paper);
for (int L=3;L<=n;L+=2)
for (int i=0;i<n-L;i++){
int j=i+L;
if ((j>=n)||(!vis[i+1][L/2])) continue;
vis[i][(L+1)/2]=Check(i,j,false,paper);
}

memset(f,0,sizeof(f));
f[0][n-1]=true;
for (int L=n-1;L>=0;L--)
for (int i=0;i<n-L;i++){
int j=i+L;
if (j>=n) continue;
for (int k=i;(k<=j)&&(!f[i][j]);k++){
if ((j+(j-k+1)<n)&&(vis[k][j-k+1])){ // 先考虑下面一块向上边折叠情况
f[i][j]|=f[i][j+(j-k+1)];
}
if ((i-(k-i+1)>=0)&&(vis[i-(k-i+1)][k-i+1])){ // 上面一块向下折叠
f[i][j]|=f[i-(k-i+1)][j];
}
}
}
ans2=0;
for (int i=0;i<n;i++)
for (int j=i;j<n;j++) ans2+=f[i][j];
if (n==1) ans2=1;

// printf("ANS1=%d  ANS2=%d\n",ans1,ans2);
return ans1*ans2;
}