QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326910#56. Nim Productckiseki75 336ms20032kbC++232.0kb2024-02-14 13:56:472024-02-14 13:56:48

Judging History

你现在查看的是最新测评结果

  • [2024-02-14 13:56:48]
  • 评测
  • 测评结果:75
  • 用时:336ms
  • 内存:20032kb
  • [2024-02-14 13:56:47]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

unsigned int SA, SB, SC;
unsigned int rng() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}

int lowbit(int x) {
  return x & -x;
}

using llu = uint32_t;
#define rep(i, r) for (int i = 0; i < r; i++)
struct NimProd {
  llu bit_prod[64][64]{}, prod[8][8][256][256]{};
  NimProd() {
    rep(i, 64) rep(j, 64) if (i & j) {
      int a = lowbit(i & j);
      bit_prod[i][j] = bit_prod[i ^ a][j] ^
        bit_prod[(i ^ a) | (a-1)][(j ^ a) | (i & (a-1))];
    } else bit_prod[i][j] = 1ULL << (i | j);
    rep(e, 8) rep(f, 8) rep(x, 256) rep(y, 256)
      rep(i, 8) if (x >> i & 1) rep(j, 8) if (y >> j & 1)
        prod[e][f][x][y] ^= bit_prod[e * 8 + i][f * 8 + j];
  }
  llu operator()(llu a, llu b) const {
    llu r = 0;
    rep(e, 4) rep(f, 4)
      r ^= prod[e][f][a >> (e*8) & 255][b >> (f*8) & 255];
    return r;
  }
};

NimProd nim_mul;

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int T;
  unsigned int lastans = 0;
  cin >> T >> SA >> SB >> SC;
  while (T--) {
    unsigned int x = rng() + lastans;
    unsigned int y = rng();
    lastans = nim_mul(x, y);
  }
  cout << lastans << '\n';
}

详细

Test #1:

score: 25
Accepted
time: 320ms
memory: 20000kb

input:

10 274134852 279286565 744539633

output:

2002382043

result:

ok single line: '2002382043'

Test #2:

score: 25
Accepted
time: 334ms
memory: 19996kb

input:

1000 734766235 309378503 610268282

output:

2106551671

result:

ok single line: '2106551671'

Test #3:

score: 25
Accepted
time: 336ms
memory: 20032kb

input:

30000 784936363 827067061 800454511

output:

554318281

result:

ok single line: '554318281'

Test #4:

score: 0
Time Limit Exceeded

input:

30000000 72129929 485897764 129463885

output:


result: