Submission #27695054

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define ll long long
using namespace std;
const int N = 307, mod = 998244353;
int n, m, dp[N][N], vis[N][N], arr[N], tp;
int f[N][N][N], pre[N][N][N];
int fi[N][N][N], st[N][N];
void init (int l, int r) {
	L(a, 0, n + 1) pre[l][a][r] = f[l][a][r];
	L(a, 1, n + 1) (pre[l][a][r] += pre[l][a - 1][r]) %= mod;
}
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 
	cin >> n >> m;
	L(i, 1, m) {
		int l, r;
		cin >> l >> r;
		vis[l][r] = true;
	}
	L(i, 0, n) {
		dp[i + 1][i] = 1, f[i][i][i + 1] = mod - 1, init (i, i + 1);
	}
	L(i, 1, n) {
		st[i + 1][i] = 1e9; 
		R(j, i, 1) st[j][i] = vis[j][i] ? j : st[j + 1][i];
	}
			
	L(i, 1, n) {
		L(l, i, n) {
			L(r, l, n) {
				if(l < r) fi[i][l][r] = fi[i][l][r - 1]; 
				else fi[i][l][r] = l;
				fi[i][l][r] = min(fi[i][l][r], st[i][r]);
//				L(u, i, l - 1) if(vis[u][r]) fi[i][l][r] = min(fi[i][l][r], u);
			} 
		}
	}
	L(len, 1, n) {
		L(l, 1, n - len + 1) {
			int r = l + len - 1;
			L(j, l, r) {
				int cr = j - 1; 
//				L(k, l - 1, j - 1) {
//					bool ok = true;
//					L(a, l, k) L(b, j, r) if(vis[a][b]) ok = false;
//					if(ok) (f[l - 1][j][r + 1] += mod - f[l - 1][k][j]) %= mod;
//				}
				cr = fi[l][j][r] - 1;
				f[l - 1][j][r + 1] = mod - pre[l - 1][cr][j];
//				L(k, l - 1, cr) (f[l - 1][j][r + 1] += mod - f[l - 1][k][j]) %= mod;
				f[l - 1][j][r + 1] = (ll) f[l - 1][j][r + 1] * dp[j + 1][r] % mod;
				(dp[l][r] += f[l - 1][j][r + 1]) %= mod;
				f[l - 1][l - 1][r + 1] = mod - dp[l][r];
			}
			init (l - 1, r + 1);
//			cout << l << ' ' << r << " : " << dp[l][r] << '\n';
//			L(x, 1, (1 << (r - l + 1)) - 1) {
//				int c = __builtin_popcount(x);
//				tp = 0;
//				arr[++tp] = l - 1;
//				L(t, l, r) if(x >> (t - l) & 1) arr[++tp] = t;
//				arr[++tp] = r + 1;
//				c = (c & 1) ? 1 : mod - 1;
//				L(j, 1, tp - 2) 
//					L(u, arr[j] + 1, arr[j + 1]) 
//						L(v, arr[j + 2], r) 
//							if(vis[u][v]) 
//								c = 0;
//				L(j, 1, tp - 1) 
//					c = (ll) c * dp[arr[j] + 1][arr[j + 1] - 1] % mod;
//				(dp[l][r] += c) %= mod;
//			}
		}
	}
	cout << dp[1][n] << '\n';
	return 0;
}

Submission Info

Judge Result