Submission #2092050


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
template<typename T, int FAC_MAX> struct Comb { vector<T> fac, ifac;
    Comb() {fac.resize(FAC_MAX, 1); ifac.resize(FAC_MAX, 1);rep(i, 1, FAC_MAX) fac[i] = fac[i - 1] * i;
        rep(i, 1, FAC_MAX) ifac[i] = T(1) / fac[i];}
    T aPb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b]; }
    T aCb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b] * ifac[b]; }
    T nHk(int n, int k) { if (n == 0 && k == 0) return T(1); if (n <= 0 || k < 0) return 0;
        return aCb(n + k - 1, k); }}; // nHk = (n+k-1)Ck
typedef ModInt<1000000007> mint;
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/





int N, K, X, Y;
int x[2050], A[1050][1050];
int cnt[5050], cnt2[5050];
int Z;
Comb<mint, 5050> com;
//---------------------------------------------------------------------------------------------------
map<int, mint> memo[1050][3030];
mint f(int n, int a1, int a2) {     // n枠にa1とa2を入れる組合せ
    if (a1 + a2 < n) return 0;
    if (n == 0 or a1 == 0 or a2 == 0) return 1;
    if (memo[n][a1].count(a2)) return memo[n][a1][a2];

    mint res = 0;
    rep(a, 0, a1 + 1) if (a <= n and n <= a + a2) res += com.aCb(n, a);
    return memo[n][a1][a2] = res;
}
//---------------------------------------------------------------------------------------------------
int solve() {
    rep(i, 0, N) cnt[x[i]]++;
    rep(y, 0, K) rep(x, 0, K) A[y][x] = min(A[y][x] ^ X, A[y][x] ^ Y);
    Z = X ^ Y;

    // 整合性チェック
    rep(y, 0, K) rep(x, 0, K) {
        if (y == x and A[y][x] != 0) return 0;
        if (y != x and A[y][x] != A[x][y]) return 0;
        if (y != x) {
            if ((A[0][x] ^ A[0][y]) == A[x][y]) continue;
            if ((A[0][x] ^ A[0][y] ^ Z) == A[x][y]) continue;
            return 0;
        }
    }

    mint ans = 0;
    rep(a0, 0, 2050) if (a0 < (a0 ^ Z)) {
        rep(i, 0, 2050) cnt2[i] = 0;
        cnt2[a0]++;
        rep(i, 1, K) cnt2[min(a0 ^ A[0][i], a0 ^ A[0][i] ^ Z)]++;
        mint d = 1;
        rep(i, 0, 2050) if (i < (i ^ Z)) d *= f(cnt2[i], cnt[i], cnt[i ^ Z]);
        ans += d;
    }
    return ans.get();
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> X >> Y;
    rep(i, 0, N) cin >> x[i];
    rep(y, 0, K) rep(x, 0, K) cin >> A[y][x];
    cout << solve() << endl;
}

Submission Info

Submission Time
Task D - XOR XorY
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 800
Code Size 5268 Byte
Status
Exec Time 144 ms
Memory 153728 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 800 / 800 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt
Case Name Status Exec Time Memory
00_example_01.txt 62 ms 149760 KB
00_example_02.txt 56 ms 149760 KB
00_example_03.txt 62 ms 149760 KB
01.txt 63 ms 149760 KB
02.txt 63 ms 149760 KB
03.txt 63 ms 149760 KB
04.txt 63 ms 149760 KB
05.txt 63 ms 149760 KB
06.txt 63 ms 149760 KB
07.txt 63 ms 149760 KB
08.txt 63 ms 149760 KB
09.txt 64 ms 149760 KB
10.txt 63 ms 149760 KB
11.txt 84 ms 151808 KB
12.txt 134 ms 153216 KB
13.txt 71 ms 151808 KB
14.txt 74 ms 151808 KB
15.txt 73 ms 151936 KB
16.txt 76 ms 151808 KB
17.txt 98 ms 151936 KB
18.txt 122 ms 152832 KB
19.txt 90 ms 151808 KB
20.txt 94 ms 151808 KB
21.txt 144 ms 153728 KB
22.txt 144 ms 153728 KB
23.txt 136 ms 153728 KB
24.txt 136 ms 153728 KB
25.txt 141 ms 153728 KB
26.txt 74 ms 151808 KB
27.txt 70 ms 151808 KB
28.txt 65 ms 151808 KB
29.txt 66 ms 151808 KB
30.txt 67 ms 151808 KB
31.txt 64 ms 151808 KB
32.txt 59 ms 151808 KB
33.txt 59 ms 151808 KB
34.txt 131 ms 153728 KB
35.txt 141 ms 153728 KB