結果

問題 No.1696 Nonnil
コンテスト
ユーザー 已经死了
提出日時 2025-08-05 21:13:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,632 bytes
コンパイル時間 994 ms
コンパイル使用メモリ 108,800 KB
実行使用メモリ 11,296 KB
最終ジャッジ日時 2025-08-05 21:13:52
合計ジャッジ時間 7,095 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 WA * 2 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Define a structure for intervals for clarity.
struct Interval {
    int l, r;
};

// Function to check if interval 'a' is a proper subset of interval 'b'.
bool is_proper_subset(const Interval& a, const Interval& b) {
    return b.l <= a.l && a.r <= b.r && (b.l < a.l || a.r < b.r);
}

// Function for modular exponentiation (base^exp % mod).
long long power(long long base, long long exp) {
    long long res = 1;
    long long mod = 998244353;
    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
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n;
    int k, m;
    std::cin >> n >> k >> m;

    std::vector<Interval> all_intervals(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> all_intervals[i].l >> all_intervals[i].r;
    }

    // Filter to get only minimal intervals.
    std::vector<Interval> minimal_intervals;
    for (int i = 0; i < m; ++i) {
        bool is_minimal = true;
        for (int j = 0; j < m; ++j) {
            if (i == j) continue;
            if (is_proper_subset(all_intervals[j], all_intervals[i])) {
                is_minimal = false;
                break;
            }
        }
        if (is_minimal) {
            minimal_intervals.push_back(all_intervals[i]);
        }
    }

    int m_minimal = minimal_intervals.size();
    long long total_count = 0;
    long long MOD = 998244353;

    // Iterate through all 2^m_minimal subsets of the minimal intervals.
    for (int i = 0; i < (1 << m_minimal); ++i) {
        std::vector<Interval> subset;
        int set_bits = 0; // This is |I| in the formula

        for (int j = 0; j < m_minimal; ++j) {
            if ((i >> j) & 1) {
                subset.push_back(minimal_intervals[j]);
                set_bits++;
            }
        }

        // Calculate the size of the union of intervals in the current subset.
        long long union_size = 0;
        if (!subset.empty()) {
            // Sort by start point to merge intervals efficiently.
            std::sort(subset.begin(), subset.end(), [](const Interval& a, const Interval& b) {
                return a.l < b.l;
            });

            int current_l = subset[0].l;
            int current_r = subset[0].r;

            for (size_t j = 1; j < subset.size(); ++j) {
                if (subset[j].l <= current_r) {
                    // Overlapping or adjacent interval, extend the current merged interval.
                    current_r = std::max(current_r, subset[j].r);
                } else {
                    // Disjoint interval, add the size of the merged interval and start a new one.
                    union_size += (current_r - current_l + 1);
                    current_l = subset[j].l;
                    current_r = subset[j].r;
                }
            }
            // Add the last merged interval.
            union_size += (current_r - current_l + 1);
        }

        long long available_numbers = k - union_size;
        
        // Calculate the term (K - |Union|)^N
        long long term = power(available_numbers, n);

        // Apply the inclusion-exclusion principle.
        if (set_bits % 2 == 1) { // If |I| is odd, subtract.
            total_count = (total_count - term + MOD) % MOD;
        } else { // If |I| is even, add.
            total_count = (total_count + term) % MOD;
        }
    }

    std::cout << total_count << std::endl;

    return 0;
}
0