結果
問題 |
No.2061 XOR Sort
|
ユーザー |
|
提出日時 | 2025-03-18 18:51:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,344 bytes |
コンパイル時間 | 2,142 ms |
コンパイル使用メモリ | 195,780 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-18 18:51:47 |
合計ジャッジ時間 | 5,016 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 WA * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MOD = 998244353; // Function to perform XOR basis reduction vector<int> getXORBasis(vector<int> &A) { vector<int> basis(30, 0); // Stores independent binary components for (int num : A) { for (int i = 29; i >= 0; i--) { if ((num >> i) & 1) { // Check if bit i is set if (!basis[i]) { basis[i] = num; // Assign as a new basis vector break; } num ^= basis[i]; // Reduce num using existing basis } } } return basis; } // Function to compute power (2^rank) % MOD long long modExp(long long base, long long exp, long long mod) { long long result = 1; while (exp > 0) { if (exp % 2 == 1) result = (result * base) % mod; base = (base * base) % mod; exp /= 2; } return result; } int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++) cin >> A[i]; // Compute XOR basis vector<int> basis = getXORBasis(A); // Count number of independent basis elements int rank = 0; for (int i = 0; i < 30; i++) { if (basis[i]) rank++; } // The number of valid sorted sequences is 2^rank % MOD cout << modExp(2, rank, MOD) << endl; return 0; }