2 条题解
-
0
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; int n, m, sum[110][110]; long long f[110][110][110], g[110][110][110], ans = 1; char s[110][110]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> s[i] + 1; // s[i][1..m] for (int k = n; k >= 1; k--) { for (int i = 1; i <= m; i++) sum[k][i] = sum[k][i-1] + (s[k][i] == 'X'); for (int i = 1; i <= m; i++) { for (int j = i; j <= m; j++) { if (sum[k][j] - sum[k][i-1] > 0) f[k][i][j] = 0; else if (k == n) f[k][i][j] = 1; else f[k][i][j] = g[k+1][i][j]; ans = (ans + f[k][i][j]) % mod; } } // g[k][i][j] for (int l = m; l >= 1; l--) { // l 是区间长度 for (int i = 1; i+l-1 <= m; i++) { int j = i+l-1; g[k][i][j] = (g[k][i-1][j] + g[k][i][j+1] - g[k][i-1][j+1] + f[k][i][j]) % mod; } } } cout << ans << endl; return 0; }
- 1
信息
- ID
- 10
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 15
- 已通过
- 6
- 上传者
