2 条题解

  • 0
    @ 2024-9-1 21:01:27

    image.pngimage

    • 0
      @ 2024-9-1 20:46:10
      #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
      上传者