QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317179#7306. Multi-stage Marathonckiseki#AC ✓298ms11140kbC++204.3kb2024-01-28 17:18:502024-01-28 17:18:50

Judging History

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

  • [2024-01-28 17:18:50]
  • 评测
  • 测评结果:AC
  • 用时:298ms
  • 内存:11140kb
  • [2024-01-28 17:18:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
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

using lld = int64_t;
const int mod = 1000000007;
int add(int a, int b) {
  return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
  return a - b < 0 ? a - b + mod : a - b;
}
void addeq(int &x, int v) {
  x = add(x, v);
}
void subeq(int &x, int v) {
  x = sub(x, v);
}
int mul(lld a, lld b) {
  return static_cast<int>(a * b % mod);
}
int modpow(int e, int p) {
  int r = 1;
  while (p) {
    if (p & 1) r = mul(r, e);
    e = mul(e, e);
    p >>= 1;
  }
  return r;
}
int modinv(int x) {
  return modpow(x, mod - 2);
}

#define rep(x, y, z) for (int x=y; x < z; x++)
using VI = vector<int>;
using VVI = vector<VI>;
void Hessenberg(VVI &H, int N) {
  for (int i = 0; i < N - 2; ++i) {
    for (int j = i + 1; j < N; ++j) if (H[j][i]) {
      rep(k, i, N) swap(H[i + 1][k], H[j][k]);
      rep(k, 0, N) swap(H[k][i+1], H[k][j]);
      break;
    }
    if (!H[i + 1][i]) continue;
    for (int j = i + 2; j < N; ++j) {
      int co = mul(modinv(H[i + 1][i]), H[j][i]);
      rep(k, i, N) subeq(H[j][k], mul(H[i+1][k], co));
      rep(k, 0, N) addeq(H[k][i+1], mul(H[k][j], co));
    }
  }
}
VI CharacteristicPoly(VVI &A) {
  int N = (int)A.size(); Hessenberg(A, N);
  VVI P(N + 1, VI(N + 1)); P[0][0] = 1;
  for (int i = 1; i <= N; ++i) {
    rep(j, 0, i+1) P[i][j] = j ? P[i-1][j-1] : 0;
    for (int j = i - 1, val = 1; j >= 0; --j) {
      int co = mul(val, A[j][i - 1]);
      rep(k, 0, j+1) subeq(P[i][k], mul(P[j][k], co));
      if (j) val = mul(val, A[j][j - 1]);
    }
  }
  if (N & 1) for (int &x : P[N]) x = sub(0, x);
  return P[N];
}

vector<int> Mul(const VVI &M, const vector<int> &p) {
  assert(p.size() == M.size());
  vector<int> q(M[0].size());
  for (size_t i = 0; i < p.size(); i++) {
    for (size_t j = 0; j < M[i].size(); j++) {
      q[j] = add(q[j], mul(M[i][j], p[i]));
    }
  }
  return q;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m, T;
  cin >> n >> m >> T;

  vector<string> g(n);
  for (int i = 0; i < n; i++) {
    cin >> g[i];
  }

  auto M = vector(n, vector(n, 0));

  for (int i = 0; i < n; i++) {
    const int cnt = ranges::count(g[i], '1');
    const int inv = modinv(cnt);
    for (int j = 0; j < n; j++) {
      if (g[i][j] == '1')
        M[i][j] = inv;
    }
  }

  auto tM = M;
  auto r = CharacteristicPoly(tM);
  orange(all(r));
  ranges::reverse(r);
  for (int x = sub(0, modinv(r[0])); int &y : r)
    y = mul(y, x);
  orange(all(r));
  const int k = (int)r.size() - 1;

  vector<int> dp(T);
  const int ord = n;

  debug(k, ord);

  vector<vector<int>> vecs(n);
  for (int v = 0; v < n; v++) {
    vector<int> p(n);
    p[v] = 1;

    vector<int> z(ord);
    for (int j = 0; j < ord; j++) {
      int cur = p[n - 1];
      p = Mul(M, p);
      z[j] = cur;
    }
    vecs[v] = z;
  }

  // auto evt = vector(T, vector(n, vector<int>()));
  for (int i = 0; i < m; i++) {
    int t, v;
    cin >> t >> v;
    --t;
    --v;
    auto z = vecs[v];
    for (int j = ord - 1; j >= 0; j--) {
      if (t + j >= k) {
        for (int s = 1; s <= k && s <= j; s++) {
          z[j] = sub(z[j], mul(r[s], z[j - s]));
        }
      }
    }
    for (int j = 0; j < ord && t + j < T; j++) {
      dp[t + j] = add(dp[t + j], z[j]);
    }
    /*
    for (int _ = k; _ < ord; _++) {
      int s = 0;
      for (int j = 1; j < k && _ - j >= 0; j++) {
        s = add(s, mul(r[j], z[_ - j]));
      }
      debug(s, z[_]);
      assert(s == z[_]);
    }
    */
  }

  for (int i = k; i < T; i++) {
    for (int j = 1; j <= k; j++) {
      dp[i] = add(dp[i], mul(r[j], dp[i - j]));
    }
  }

  orange(all(dp));

  int ans = 0;
  for (int i = 0; i < T; i++)
    ans ^= dp[i];
  cout << ans << '\n';

  return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

2 2 2
11
11
1 1
2 2

output:

500000005

result:

ok 1 number(s): "500000005"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

3 1 6
110
011
101
1 1

output:

191901811

result:

ok 1 number(s): "191901811"

Test #3:

score: 0
Accepted
time: 37ms
memory: 3668kb

input:

70 1000 10000
1000000000000000000000000000000100000000100000000000000100000000000000
0110000000000001100000100000000000000001000000010000000000000000000000
0010000000000000000000000000000000000000000000000000000000000000000000
0001000000000000000000000000001000000000000000000000000000000000100000
00...

output:

1026871829

result:

ok 1 number(s): "1026871829"

Test #4:

score: 0
Accepted
time: 41ms
memory: 3720kb

input:

70 1000 10000
1000000000000000000000000000000000000000000000000000000001000001010000
0100000000000000000000000000000010000000000000000000000000000000000000
0010000000000000000000010100000001000001000000000000000010000000000000
0001000000000000000010000000000000010000000000000000000000000000000000
00...

output:

743579645

result:

ok 1 number(s): "743579645"

Test #5:

score: 0
Accepted
time: 41ms
memory: 3664kb

input:

70 1000 10000
1100000001000100000000000001110000000000000100000000000001000000000100
0110010000000100000000000100000000100000100000000000000000000000010001
0010000010000000000000000000000000001000000000000000000100010000000000
1001100010100000001000010000000000000001000000000000010000000000001000
00...

output:

362752022

result:

ok 1 number(s): "362752022"

Test #6:

score: 0
Accepted
time: 41ms
memory: 3664kb

input:

70 1000 10000
1010000100000010100001010000100000000010000110110000000000000000001000
0101000010000100001010101010010000000000000000000000001011011010000100
0010001010001100000010010001001001101100010110100010001000000010000000
0101000001100010101010101101000100000101110010000100100010100110000001
00...

output:

69495152

result:

ok 1 number(s): "69495152"

Test #7:

score: 0
Accepted
time: 42ms
memory: 3660kb

input:

70 1000 10000
1110001110101011001011011010000110000110001100010010110011111100001000
1101110110001010001111001101010100001001101010001100101111010011010001
1010011100110110110001001011100110101101111110001100101010100111101110
1001001001000111110100001000001011001000111101111101000001111111110111
00...

output:

976173806

result:

ok 1 number(s): "976173806"

Test #8:

score: 0
Accepted
time: 41ms
memory: 3656kb

input:

70 1000 10000
1111111111011111111100101011001011111101100111111111111111101011011111
1110111111100100101111111101111110111111100111110000101111101101101111
1111110111111110101000110011110111101111110111111111111111011110111011
1111011111001110111110101111111100011101111100110111011111111011001010
11...

output:

407126826

result:

ok 1 number(s): "407126826"

Test #9:

score: 0
Accepted
time: 41ms
memory: 3932kb

input:

70 1000 10000
1111110101111111110111111111111111111101111010110111111111111111011111
1111011111111111111111111011111111111111111111110111111111111111111111
1110110111101100111111011110111111111111101111111111111111111111111111
1111111111111111110111111111111110111111011011111111101111111010011111
01...

output:

95235184

result:

ok 1 number(s): "95235184"

Test #10:

score: 0
Accepted
time: 42ms
memory: 3732kb

input:

70 1000 10000
1111110111110111111111111111111111111111111111101111111111111111101111
1111111011111011111111111111111111111111111111111111111111111111111111
1111111111111111111011111111110111111111111011111111111111011111111111
1111110111111111111111111011101110101111111111111111101111101111111111
11...

output:

137040690

result:

ok 1 number(s): "137040690"

Test #11:

score: 0
Accepted
time: 41ms
memory: 3744kb

input:

70 1000 10000
1111111111111111111111111111111111111111111111111111111111111111111111
1111111101111011111101111111111011111111111111111111111110011111111111
1111111111111111101111111111111110111011111111011111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
11...

output:

918692147

result:

ok 1 number(s): "918692147"

Test #12:

score: 0
Accepted
time: 292ms
memory: 11080kb

input:

70 10000 2000000
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111...

output:

154305482

result:

ok 1 number(s): "154305482"

Test #13:

score: 0
Accepted
time: 291ms
memory: 11012kb

input:

70 10000 2000000
1000010000000000000000000001000000000000000000000000000010000000000000
0100000000000000000000010000000001000010000000000000000000000000000000
0010000000000000000000100000000001001000000000000000000000000000010000
0001000000100000000000000000000000000000000000000000000100000000000000...

output:

601860703

result:

ok 1 number(s): "601860703"

Test #14:

score: 0
Accepted
time: 288ms
memory: 10988kb

input:

70 10000 2000000
1000000000000000010000000001000000000100000000000000001000000000000000
0110000001000000000000000010000000000000000001000001000000000000000000
0010000000110000010010001000000000000000000000101100000000000000000100
0001000000000000010000000000000000000101000100010000000000010010000000...

output:

632681263

result:

ok 1 number(s): "632681263"

Test #15:

score: 0
Accepted
time: 294ms
memory: 11032kb

input:

70 10000 2000000
1000100000100000000000000000000000000001000000011010110000000000100000
1100100010000000000000101000000000000000000000000001000000000000000000
0010000000000001000000000000000001000000000000010000000000000001000000
0001000000001000000000000010100100000000000000000001000100000000001000...

output:

50850594

result:

ok 1 number(s): "50850594"

Test #16:

score: 0
Accepted
time: 289ms
memory: 11012kb

input:

70 10000 2000000
1100000001001000001000100000010000100001000111000001110001100000000100
0110001100000011000001100000001100010100010100010000101100101110001100
0110000100110010001000100000010000010100010000000000000101000101000000
0101000100011010100000000010000010100000011100100000110101001010001100...

output:

117421938

result:

ok 1 number(s): "117421938"

Test #17:

score: 0
Accepted
time: 279ms
memory: 11016kb

input:

70 10000 2000000
1011001110101010010100110110100011001101010001100011111010101111100100
1111000000100001000100100111000011111011110111111000110100101010011010
0011110100101011000000010000100011110100011111001000100010110111110011
0001000111111000001100100110110010110000001010000101110110000000011011...

output:

671321149

result:

ok 1 number(s): "671321149"

Test #18:

score: 0
Accepted
time: 287ms
memory: 11092kb

input:

70 10000 2000000
1111111111101011101101111111011111100111111111001111011100111111110110
0111011001011100111100111111100101101111111101100111100011111111111101
1010111111111110111111111110110110111110111011100111000001111011110100
1111110100101010101111010111101111111111111111111111011101011111101111...

output:

714929330

result:

ok 1 number(s): "714929330"

Test #19:

score: 0
Accepted
time: 292ms
memory: 11088kb

input:

70 10000 2000000
1001111111111111111111111110111111011111111011011111111101111111111111
1110101111011110111111111111111111111111111111110111111111111111110110
1011010110101111111101111111111011111111111110111111100101111111100111
1111111110111111111111100111111100111111101111110101011101111110110111...

output:

706080518

result:

ok 1 number(s): "706080518"

Test #20:

score: 0
Accepted
time: 298ms
memory: 11092kb

input:

70 10000 2000000
1111111111111111111111111111111101111110111111111111111111111111111111
1111110111111111111111111111111111111111111111111111111111101111110111
1111111101111111111111111111111111111111111111111111101011111111111111
1111111111111111111111111111111111111111111111111111111111111111111111...

output:

456121666

result:

ok 1 number(s): "456121666"

Test #21:

score: 0
Accepted
time: 292ms
memory: 11140kb

input:

70 10000 2000000
1111110111111111111111111111111111111111111111111111111111111111111111
1101111111111111111101111111111111111111111110111111111111111110111111
1111111111111111111111111111111111111111111111011111111111111111111111
1111111111111111111111111111111111111111111111111111111110111011111011...

output:

964660092

result:

ok 1 number(s): "964660092"

Extra Test:

score: 0
Extra Test Passed