#325275 (C++14) No.803 Very Limited Xor Subset

提出ソース

結果

問題	No.803 Very Limited Xor Subset
ユーザー	hitonanode
提出日時	2019-03-17 23:29:24
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	375 ms / 2,000 ms
コード長	5,195 bytes
コンパイル時間	1,939 ms
コンパイル使用メモリ	177,604 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-08 03:27:58
合計ジャッジ時間	11,477 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	239 ms 5,376 KB
testcase_15	AC	260 ms 5,376 KB
testcase_16	AC	252 ms 5,376 KB
testcase_17	AC	259 ms 5,376 KB
testcase_18	AC	258 ms 5,376 KB
testcase_19	AC	253 ms 5,376 KB
testcase_20	AC	262 ms 5,376 KB
testcase_21	AC	257 ms 5,376 KB
testcase_22	AC	256 ms 5,376 KB
testcase_23	AC	375 ms 5,376 KB
testcase_24	AC	354 ms 5,376 KB
testcase_25	AC	360 ms 5,376 KB
testcase_26	AC	362 ms 5,376 KB
testcase_27	AC	355 ms 5,376 KB
testcase_28	AC	350 ms 5,376 KB
testcase_29	AC	353 ms 5,376 KB
testcase_30	AC	360 ms 5,376 KB
testcase_31	AC	362 ms 5,376 KB
testcase_32	AC	360 ms 5,376 KB
testcase_33	AC	357 ms 5,376 KB
testcase_34	AC	3 ms 5,376 KB
testcase_35	AC	331 ms 5,376 KB
testcase_36	AC	72 ms 5,376 KB
testcase_37	AC	140 ms 5,376 KB
testcase_38	AC	6 ms 5,376 KB
testcase_39	AC	6 ms 5,376 KB
testcase_40	AC	348 ms 5,376 KB
testcase_41	AC	339 ms 5,376 KB
testcase_42	AC	333 ms 5,376 KB
testcase_43	AC	331 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	2 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> void mmax(T &m, const T q) { if (m < q) m = q; }
template<typename T> void mmin(T &m, const T q) { if (m > q) m = q; }
template<typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

constexpr lint MOD = 1000000007;

// Solve ax+by=gcd(a, b)
lint extgcd(lint a, lint b, lint &x, lint &y)
{
    lint d = a;
    if (b != 0) d = extgcd(b, a % b, y, x), y -= (a / b) * x;
    else x = 1, y = 0;
    return d;
}
// Calc a^(-1) (MOD m)
lint mod_inverse(lint a, lint m)
{
    lint x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

vector<vector<lint>> gauss_jordan(vector<vector<lint>> mtr, lint mod)
{
    // Gauss-Jordan elimination 行基本変形のみを用いるガウス消去法
    int H = mtr.size(), W = mtr[0].size(), c = 0;
    REP(h, H)
    {
        if (c == W) break;
        int piv = -1;
        FOR(j, h, H) if (mtr[j][c])
        {
            if (piv == -1 or abs(mtr[j][c]) > abs(mtr[piv][c])) piv = j;
        }
        if (piv == -1) { c++; h--; continue; }
        swap(mtr[piv], mtr[h]);
        if (h != piv) REP(w, W) mtr[piv][w] = mtr[piv][w] ? mod - mtr[piv][w] : 0; // 行列式符号不変
        lint pivinv = mod_inverse(mtr[h][c], mod);
        FOR(hh, h + 1, H) IFOR(w, c, W) mtr[hh][w] = (mtr[hh][w] - mtr[h][w] * mtr[hh][c] % mod * pivinv % mod + mod) % mod;
        c++;
    }
    return mtr;
}

int rank_gauss_jordan(const vector<vector<lint>> &mtr)
{
    // gauss_jordanを実行した後の行列のランク計算
    IREP(h, mtr.size()) for (auto v : mtr[h]) if (v) return h + 1;
    return 0;
}

lint power(lint x, lint n, lint MOD)
{
    lint ans = 1;
    while (n>0)
    {
        if (n & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
       n >>= 1;
    }
   return ans;
}

constexpr int D = 31;
int main()
{
    lint N, M, X;
    cin >> N >> M >> X;
    vector<lint> A(N);
    cin >> A;
    vector<vector<lint>> mat(D + M, vector<lint>(N + 1));
    vector<lint> v(D + M);
    REP(d, D) v[d] = ((X >> d) & 1);
    REP(i, N) REP(d, D) mat[d][i] = ((A[i] >> d) & 1);
    
    REP(j, M)
    {
        int t, l, r;
        cin >> t >> l >> r;
        FOR(k, l - 1, r) mat[D + j][k] = 1;
        v[D + j] = t;
    }
    REP(j, D + M) mat[j][N] = v[j];

    auto mat2 = gauss_jordan(mat, 2);

    int h1 = 0, h2 = 0;
    REP(i, N) REP(j, D + M) if (mat2[j][i]) mmax(h1, j);
    REP(j, D + M) if (mat2[j][N]) mmax(h2, j);
    if (h2 > h1)
    {
        cout << 0 << endl;
        return 0;
    }
    for (auto &vec : mat2) vec.pop_back();
    int rnk = rank_gauss_jordan(mat2);

    cout << power(2, N - rnk, MOD) << endl;
}

yukicoder

結果

テストケース

ソースコード