TwoConvexShapes
作者：沈睿
关键词：容斥、计数、递推
题目简述
给你一个的矩阵，矩阵中有些格子只能被染成黑色，有些格子只能被染成白色，而有些格子两种颜色均可被染上。但合法染色方案必须满足任意两个同颜色格子之间的格子也必须是该颜色。问合法染色方案数，对取模。
数据范围：
题解
我们来观察一下最后的成图要满足怎样的条件才是合法的。
我们不难发现成图必须满足以下几个条件：
1、黑色和白色的格子各自形成了一个联通块。
2、对于每行黑块白块的分界处由上自下形成了一个单调不降或单调不增的序列。
于是我们可以根据这个单调不降或者单调不增的性质进行计数。
我们不妨先行统计，
黑色居于左侧，而且分界点单调不降的方案数，可以写出如下递推式：
其中是指第行中，位置到的位置均满足染成黑色的条件，位置到位置均满足染成白色的条件。
这个递推暴力是的，但我们可以进行如下的前缀和优化做到：
同理，
白色居于左侧，分界点单调不降
黑色居于左侧，分界点单调不增
白色居于左侧，分界点单调不增
以上三种情况，都可以用如上讲述的方法进行统计。
但是不难发现，我们的统计当中有一些重复，不妨让我们一一列举一下：
每行都是同种颜色，而且黑色居于上方的的方案，在情况下被重复计算过，固然减去。
同理，每行都是同种颜色，而且白色居于上方的的方案，在情况下被重复计算过，固然减去。
每列都是同种颜色，而且黑色居于左侧的的方案，在情况下被重复计算过，固然减去。
同理，每列都是同种颜色，而且白色居于左侧的的方案，在情况下被重复计算过，固然减去。
全黑的方案数，在被计入过，在中被减去过，固然计入。
同理，全白的方案数，在被计入过，在中被减去过。固然计入。
总的来说，这是一道很好（丧心病狂）的计数题，充分锻炼了选手的观察（乱搞）能力和代码（口胡）能力。
我写的代码时间复杂度为，但对于程序的细节进行更好的把握，可以优化到，在此不多赘述。
代码
#include<bits/stdc++.h>
#define FT first
#define SC second
#define PB push_back
#define MP make_pair
#define REP(i, l, r) for(int i = (l); i <= (r); i++)
#define PER(i, r, l) for(int i = (r); i >= (l); i--)
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define ROF(i, n) for(int i = (n) - 1; i >= 0; i--)
#define VEP(i, x) for(int i = 0; i < x.size(); i++)
#define DFOR(i, x, y) for(int i = hd[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to)
#define MEM(a, b) memset(a, b, sizeof(a))
#define rint read<int>()
#define rll read<LL>()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PI;
const int inf = 0x7fffffff;
const int MOD = 1000000007;
template <typename tn> inline void cmax(tn &a, tn b){ if (a < b) a = b; }
template <typename tn> inline void cmin(tn &a, tn b){ if (a > b) a = b; }
const int N = 50 + 5;
class TwoConvexShapes
{
public:
int f[N][N], can[N][N], ans, n, m;
char a[N][N];
void Non_decreasing(){//由上至下单调不降的情况
REP(i, 0, m) f[0][i] = 1;
REP(i, 1, n) REP(j, 0, m){
f[i][j] = j ? f[i][j - 1] : 0;
if (can[i][j]) f[i][j] = (f[i][j] + f[i - 1][j]) % MOD;
}
ans = (ans + f[n][m]) % MOD;
}
void Non_increasing(){//有上至下单调不增的情况
REP(i, 1, n / 2) REP(j, 0, m) swap(can[i][j], can[n - i + 1][j]);
Non_decreasing();
REP(i, 1, n / 2) REP(j, 0, m) swap(can[i][j], can[n - i + 1][j]);
}
void Exclusion_row(){//考虑每列的数都一样的情况。
REP(j, 0, n){
int flag = 1;
REP(i, 1, j) if (!can[i][m]) { flag = 0; break; }
REP(i, j + 1, n) if (!can[i][0]) { flag = 0; break; }
ans -= flag;
}
}
void Exclusion_column(){//考虑每行的数都一样的情况
REP(j, 0, m){
int flag = 1;
REP(i, 1, n) flag &= can[i][j];
ans -= flag;
}
}
void Exclusion_all(){//所有格子颜色都相同的情况
REP(i, 1, n) REP(j, 1, m) if (a[i][j] == 'W') return;
++ans;
}
void UpdateAns(){
REP(i, 1, n) REP(j, 0, m){
can[i][j] = 1;
REP(k, 1, j) if (a[i][k] == 'W') {can[i][j] = 0; break;}
REP(k, j + 1, m) if (a[i][k] == 'B') {can[i][j] = 0; break;}
}
Non_decreasing();
Non_increasing();
Exclusion_row();
Exclusion_column();
Exclusion_all();
}
int countWays(vector <string> grid)
{
n = grid.size(), m = grid[0].size(), ans = 0;
REP(i, 1, n) REP(j, 1, m) a[i][j] = grid[i - 1][j - 1];
UpdateAns();
//由于颜色是相对的，在10种情况中黑白各占一半，将黑色和白色交换再做一次统计可以省略很多代码
REP(i, 1, n) REP(j, 1, m)
if (a[i][j] == 'B') a[i][j] = 'W'; else
if (a[i][j] == 'W') a[i][j] = 'B';
UpdateAns();
return (ans + MOD) % MOD;
}
};