提出 #2092050


ソースコード 拡げる

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;
}

提出情報

提出日時
問題 D - XOR XorY
ユーザ hamayanhamayan
言語 C++14 (GCC 5.4.1)
得点 800
コード長 5268 Byte
結果
実行時間 144 ms
メモリ 153728 KB

テストケース

セット名 得点 / 配点 テストケース
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
ケース名 結果 実行時間 メモリ
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