Submission #1062368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062368		vjudge1	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	2036 ms	2136 KiB

xorsum

#include <cstdio>
#include <array>
#include <vector>
#include <utility>
using namespace std;
template<typename T>
using ve = vector<T>;
using ii = pair<int, int>;
using ll = long long;
template <typename T, int sz>
using ar = array<T, sz>;

constexpr ll M = 1000000007;
constexpr int N = 1005;

ar<int, N> fac, ifac;

ar<int, N> eve, odd;

ll bpow(ll a, ll b) {
  if (!b) return 1;
  ll r { bpow(a, b / 2) };
  if (b & 1) return r * r % M * a % M;
  return r * r % M;
}

ll ncr(int n, int r) {
  if (n < r) return 0;
  return fac[n] * 1ll * ifac[r] % M * 1ll * ifac[n - r] % M;
}

ll gauss(int n) {
  return ncr(n + 1, 2);
}

void init() {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * 1ll * i % M, ifac[i] = bpow(fac[i], M - 2);
  
  for (int i = 0; i < N; ++i)
    for (int j = 0; j <= i; ++j)
      if (j & 1)
        odd[i] = (odd[i] + ncr(i, j)) % M;
      else
        eve[i] = (eve[i] + ncr(i, j)) % M;
}

int main() {
  init();

  int n, q;
  scanf("%d", &n);
  ve<int> a(n);
  for (auto &x : a) scanf("%d", &x);

  scanf("%d", &q);
  ve<ar<int, 3 >> b(q);
  for (auto &[l, r, x] : b) scanf("%d%d%d", &l, &r, &x);

  ll ans { };

  for (int ii = 0; ii < (1 << q); ++ii) {
    static ll aa[102], ab[102];
    for (int i = 0; i <= n; ++i)
      aa[i] = 0;
    for (int j = 0; j < q; ++j) {
      if (ii & (1 << j)) {
        aa[b[j][0]] ^= b[j][2];
        aa[b[j][1] + 1] ^= b[j][2];
      }
    }
    for (int i = 1; i <= n; ++i) aa[i] ^= aa[i - 1], ab[i] = ab[i - 1] + (a[i - 1] ^ aa[i]);
    for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j)
      ans = (ans + (ab[j] - ab[i - 1]) * (ab[j] - ab[i - 1]) % M) % M;
  }

  printf("%lld", ans);
  return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
xorsum.cpp:55:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   for (auto &x : a) scanf("%d", &x);
      |                     ~~~~~^~~~~~~~~~
xorsum.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
xorsum.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   for (auto &[l, r, x] : b) scanf("%d%d%d", &l, &r, &x);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8