結果
問題 |
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 |
ソースコード
#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; }