Submission #67657700

---

Source Code Expand

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// The modulus for the final sum
const int MOD = 998244353;

// Modular exponentiation to compute (base^exp) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M;
    cin >> N >> M;

    vector<vector<bool>> is_movie(N + 1, vector<bool>(N + 1, false));
    for (int k = 0; k < M; ++k) {
        int l, r;
        cin >> l >> r;
        is_movie[l][r] = true;
    }
    
    // **FIX 1: Correctly precompute movie counts inside intervals [i, j]**
    vector<vector<int>> movie_counts(N + 2, vector<int>(N + 2, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = i; j <= N; ++j) {
            int count_ending_at_j = 0;
            for (int l = i; l <= j; ++l) {
                if (is_movie[l][j]) {
                    count_ending_at_j++;
                }
            }
            movie_counts[i][j] = movie_counts[i][j - 1] + count_ending_at_j;
        }
    }
    
    vector<long long> pow2(M + 1);
    pow2[0] = 1;
    for (int i = 1; i <= M; ++i) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }

    // **FIX 2: Use the standard O(N^2) DP recurrence for deficiencies**
    // dp[i][j] will store the sum of deficiencies for movies within interval [i, j]
    vector<vector<long long>> dp(N + 2, vector<long long>(N + 2, 0));

    for (int len = 1; len <= N; ++len) {
        for (int i = 1; i <= N - len + 1; ++i) {
            int j = i + len - 1;
            
            // Base deficiency from the whole interval [i, j] being a conflicting core
            long long h_val = 0;
            if (movie_counts[i][j] > len) {
                // Deficiency = (|s'| - len) * 2^(M-|s'|)
                h_val = (long long)(movie_counts[i][j] - len) * pow2[M - movie_counts[i][j]] % MOD;
            }
            
            // Deficiencies from proper sub-intervals via Principle of Inclusion-Exclusion
            long long sub_deficiencies = (dp[i+1][j] + dp[i][j-1]) % MOD;
            sub_deficiencies = (sub_deficiencies - dp[i+1][j-1] + MOD) % MOD;
            
            dp[i][j] = (h_val + sub_deficiencies) % MOD;
        }
    }
    
    // Total sum = (sum of all |s|) - (sum of all deficiencies)
    long long sum_of_sizes = (M * power(2, M - 1)) % MOD;
    long long total_deficiency = dp[1][N];

    long long final_answer = (sum_of_sizes - total_deficiency + MOD) % MOD;

    cout << final_answer << endl;

    return 0;
}

Submission Info

Judge Result