总述
此题用区间 dp 解决，二维前缀和优化。
朴素做法
阶段：自上而下数每一层。
状态：\(dp_{i,l,r}\) 表示自上而下数第 \(i\) 行中在 \([l,r]\) 摆积木的方案数。
状态转移方程：根据题意可知，若要在 \([l,r]\) 中摆积木，那么 \([l,r]\) 中不允许有 \(\tt{X}\)，而第 \(i\) 层的 \([l,r]\) 要摆积木，就需要第 \(i+1\) 层的来托住。因此方程为：
\[dp_{i,l,r}=\sum_{x=1}^l \sum_{y=r}^m dp_{i+1,x,y} \]初始化：很明显，若第 \(n\) 层的 \([l,r]\) 中没有 \(\tt{X}\)，那么 \(dp_{n,l,r}=1\)，否则为 \(0\)，而对于判断是否合法，可将每一行做一个一维前缀和，这样可以 \(O(1)\) 判断。
答案：所有 \(dp_{i,l,r}\) 之和，即：
\[1+ \sum_{i=1}^n \sum_{l=1}^{m} \sum_{r=l}^m dp_{i,l,r} \]时间复杂度：这样的时间复杂度为 \(O(nm^4)\)，无法承受，考虑优化。
二维前缀和优化
观察状态转移方程，可用二维前缀和优化，将所有的 \(dp_{i+1,l,r}\) 视作一个点，因为都在第 \(i+1\) 层，因此可以用滚动数组优化掉一维。那么 \(\sum_{x=1}^l \sum_{y=r}^m dp_{i+1,x,y}\) 就是矩阵 \((1,r) \sim (l,m)\) 的和。
时间复杂度二维前缀和是 \(O(m^2)\)，而转移可以 \(O(1)\)，因此时间复杂度为 \(O(nm^2)\)，足矣通过本题。
#include <cstdio>
#define ll long long
const int N=105;
const int M=105;
const int mod=1e9+7;
int n,m;
ll ans=1;
char mp[N][M];
int c[N][M];
ll dp[N][M][M];
ll sum[M][M];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf(" %s",mp[i]);
for(int j=0;j<m;j++) c[i][j+1]=c[i][j]+(mp[i][j]=='X');//一维前缀和优化
}
for(int l=1;l<=m;l++) {
for(int r=l;r<=m;r++) {
if(!(c[n][r]-c[n][l-1])) dp[n][l][r]=1;//初始化
ans+=dp[n][l][r];
ans%=mod;
}
}
for(int i=n-1;i>=1;i--) {//阶段
for(int l=1;l<=m;l++) {//二维前缀和优化
for(int r=1;r<=m;r++) sum[l][r]=(dp[i+1][l][r]+sum[l][r-1]+sum[l-1][r]-sum[l-1][r-1])%mod;
}
for(int len=1;len<=m;len++) {//状态
for(int l=1;l+len-1<=m;l++) {
int r=l+len-1;
if(c[i][r]-c[i][l-1]) continue;
dp[i][l][r]=(sum[l][m]-sum[l][r-1]-sum[0][m]+sum[0][r-1])%mod;//决策
ans+=dp[i][l][r];
ans%=mod;
}
}
}
printf("%lld\n",(ans+mod)%mod);//答案可能会出现负数，前面加减乘除取模过多
return 0;
}