评测记录 - 洛谷

评测记录 - LOJ

不知道为啥，官方数据稳过，甚至交到 LOJ 上最慢一个点跑了不到 100ms，但是洛谷民间数据最后两个点 TLE.

前缀和 + 乘法计数做法，附上代码：

#include<bits/stdc++.h>
using namespace std;

const int mod = 998244353;

char c[1024][1024];
int s[1024][1024];
int s2[1024][1024];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T, id;
	cin >> T >> id;
	while(T--)
	{
		int n, m, xc, xf;
		cin >> n >> m >> xc >> xf;
		int ansc = 0, ansf = 0;
		for(int i = 0; i <= n; i++)
		{
			for(int j = 0; j <= m; j++)
			{
				c[i][j] = 0;
				s[i][j] = 0;
				s2[i][j] = 0;
			}
		}
		for(int i = 0; i < n; i++)
		{
			cin >> c[i];
		}
		for(int i = 0; i < n; i++)
		{
			if(c[i][m-1] == '0')
			{
				s[i][m-1] = 1;
			}
		}
		for(int i = 0; i < n; i++)
		{
			for(int j = m - 2; j >= 0; j--)
			{
				if(c[i][j] == '0')
				{
					if(c[i][j+1] == '0')
					{
						s[i][j] = s[i][j+1] + 1;
					}
					else
					{
						s[i][j] = 1;
					}
				}
			}
		}
		for(int j = 0; j < m; j++)
		{
			if(c[n-1][j] == '0')
			{
				s2[n-1][j] = 1;
			}
		}
		for(int j = 0; j < m; j++)
		{
			for(int i = n - 2; i >= 0; i--)
			{
				if(c[i][j] == '0')
				{
					if(c[i+1][j] == '0')
					{
						s2[i][j] = s2[i+1][j] + 1;
					}
					else
					{
						s2[i][j] = 1;
					}
				}
			}
		}
		for(int i = 0; i < n - 1; i++)
		{
			for(int j = 0; j < m - 1; j++)
			{
				if(s[i][j] <= 1 || c[i+1][j] == '1')	continue;
				for(int k = i + 2; k < n; k++)
				{
					if(c[k][j] == '1')	break;
					ansc += s[i][j+1] * s[k][j+1];
					ansc %= mod;
					if(k + 1 < n)
					{
						ansf +=  s[i][j+1] * s[k][j+1] * s2[k+1][j];
						ansf %= mod;
					}
				}
			}
		}
		cout << xc * ansc % mod << ' ' << xf  * ansf % mod << '\n';
	}
}