Submission #27743665

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define per(i, a, n) for (ll i = n - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

vector<int> vle[305];       // [r pos] = {l pos...} 区间右端点到左端点
ll dp[305][305][305];   // [l][r][x] = [l..r] 最大的是x的方案数, 其中不论l取值多少,x与[l,r]至少属于[l,r]中的一个完整区间
ll rdp[305][305][305];  // dp 前缀和
// 默认 全false, 在[l..r]之间 是否存在完整区间
bool exi[305][305];
int cl[305];  // 右端点 in [i..最右测] = 区间的最小左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l);
  }
  rep(i, 1, n+1) sort(all(vle[i]));
  rep(len, 2, n+1) {              // 枚举 长度
    rep(r, len, n+1) {            // 右端点 从小到大
      int l = r - len + 1;        // 左侧端点 = 右端点 - 长度 +1
      int nw = r + 1;             // 左端点, 在[l..r] 中
      per(j, l, r + 1) {          // j（右端点）从大到小 [l,r] 范围内的每个右端点
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) nw = min(nw, vle[j][t]);
        cl[j] = nw;
      }
      if (nw == r+1) {            // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;           // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r+1) {            // [l..x-1]x[x+1..r]
        if (x < cl[x]) continue;  // 不存在 [l,r] 之间的小区间 包含 坐标x
        // 注意这里, 当[l..x-1]不存在时是1, 而[l..x-1]存在时,因为防止重复统计可能[cl[x]..x-1]是0
        ll sl = exi[l][x-1] ? rdp[l][x-1][x-1] - rdp[l][x-1][cl[x]-1] : 1;
        // 而对于右侧 似乎可以直接判断前缀和是否非零,但实际上因为是取mod运算,可能为mod的倍数,所以还是需要一个exi的辅助数组
        ll sr = exi[x+1][r] ? rdp[x+1][r][r] - rdp[x + 1][r][x] : 1;
        dp[l][r][x] = ((sl%mod) * (sr%mod))%mod;    // [l,r-1]中 最大的下标为x, 方案数
      }
      rep(j, l, r + 1) rdp[l][r][j] = (rdp[l][r][j-1] + dp[l][r][j])%mod;
    }
  }
  printf("%lld", (rdp[1][n][n]+mod)%mod); // [0,n-1] 最大下标[0..n-1]的方案数
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:30:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   30 |         if (t < vle[j].size()) nw = min(nw, vle[j][t]);
      |             ~~^~~~~~~~~~~~~~~
./Main.cpp:17:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
./Main.cpp:20:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%d %d", &l, &r);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Judge Result