QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#449910#7647. 树哈希JWRuixi0 2285ms1485816kbC++208.1kb2024-06-21 19:06:242024-06-21 19:06:24

Judging History

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

  • [2024-06-21 19:06:24]
  • 评测
  • 测评结果:0
  • 用时:2285ms
  • 内存:1485816kb
  • [2024-06-21 19:06:24]
  • 提交

answer

// algorithm 4-i
#ifdef LOCAL
#include "S:\Codes\VSCode\algo\Lib\Tools\debug.h"
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 1e2 + 9;
int n, q, P;

using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

template<class T>
IL int siz (const vector<T> &v) {
  return (int)(v.size());
}

struct barrett {
  unsigned m;
  u64 B;
  explicit barrett () : m(0), B(0) {}
  explicit barrett (u32 _m) : m(_m), B((u64)(-1) / _m + 1) {}
  u32 mod () const { return m; }
  u32 rem (u64 z) const {
    static u64 x, y;
    x = (u64)(((u128)(z) * B) >> 64);
    y = x * m;
    return z - y + (z < y ? m : 0);
  }
} bt;

template<class T>
IL void qm (T &x) {
  x += (x >> 31) & P;
}

template<class T>
IL T qpow (T b, unsigned k = P - 2) {
  T r = 1;
  for (; k; k >>= 1, b = bt.rem(u64(b) * b)) if (k & 1) r = bt.rem(u64(r) * b);
  return r;
}

struct mint {
  int v;
  
  mint (int _v = 0) : v(_v) {}

  mint inv () const { return qpow(v, P - 2); }
#define DEF(o, e) \
  mint& operator o##= (const mint &rhs) { e; return *this; } \
  mint operator o (const mint &rhs) const { return mint(*this) o##= rhs; }
  DEF(+, qm(v += rhs.v - P))
  DEF(-, qm(v -= rhs.v))
  DEF(*, v = bt.rem((u64)v * rhs.v))
  DEF(/, *this *= rhs.inv())
#undef DEF
  mint pow (unsigned k) const {
    int r = 1;
    u64 b = v;
    for (; k; k >>= 1, b = b * b % P) if (k & 1) r = r * b % P;
    return r;
  }
};

IL mint sgn (int sz) {
  return sz & 1 ? P - 1 : 1;
}

mint fc[N], ifc[N], iv[N], C[N][N], pq[N], pw[N][N];

void init () {
  fc[0] = 1;
  L (i, 1, n) {
    fc[i] = fc[i - 1] * i;
  }
  ifc[n] = fc[n].inv();
  R (i, n - 1, 0) {
    ifc[i] = ifc[i + 1] * (i + 1);
  }
  iv[0] = iv[1] = 1;
  L (i, 2, n) {
    iv[i] = ifc[i] * fc[i - 1];
  }
  L (i, 0, n) {
    C[i][0] = 1;
    L (j, 1, i) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
  }
  pw[0][0] = 1;
  L (i, 1, n) {
    pw[i][0] = 1;
    L (j, 1, n) {
      pw[i][j] = pw[i][j - 1] * i;
    }
  }
  pq[0] = 1;
  L (i, 1, n) {
    pq[i] = pq[i - 1] * q;
  }
}

constexpr int M = 30000;
int tot;
vi st[M], fx[M];
int len[M], big[M];

unordered_map<u32, int> idxx, idss;

IL int& ids (const vi &v) {
  static constexpr int B = 37;
  u32 s = 0;
  L (i, 0, siz(v) - 1) {
    s = bt.rem(u64(s) * B + v[i]);
  }
  return idss[s];
}

IL int& idx (const vi &v) {
  static constexpr int B = 29;
  u32 s = 0;
  L (i, 0, siz(v) - 1) {
    s = bt.rem(u64(s) * B + v[i]);
  }
  return idxx[s];
}

vi sp[M][N / 2];

void search (int L) {
  priority_queue<pair<int, vi>> q;
  q.emplace(0, vi{});
  while (!q.empty()) {
    auto [s, u] = q.top();
    s = -s;
    q.pop();
    idx(u) = ++tot;
    st[tot] = u;
    len[tot] = s;
    big[tot] = siz(u) ? u.back() : 0;
    L (i, siz(u) ? u.back() : 1, L - s) {
      auto v = u;
      v.eb(i);
      q.emplace(-s - i, v);
    }
  }
  L (i, 1, tot) {
    fx[i].resize(L + 1);
    for (int j : st[i]) {
      ++fx[i][j];
    }
    ids(fx[i]) = i;
  }
  L (u, 1, tot) {
    L (t, 1, L) {
      int U = (L - len[u]) / t + fx[u][t];
      sp[u][t].resize(U + 1);
      auto v = fx[u];
      L (k, 0, U) {
        v[t] = k;
        sp[u][t][k] = ids(v);
      }
    }
  }
}

namespace Poly {
  mint f[N];

  void Ln (mint *g, int n) {
    L (i, 0, n) {
      f[i] = 0;
    }
    L (i, 1, n) {
      f[i] = g[i] * i;
      L (j, 1, i - 1) {
        f[i] -= f[j] * g[i - j];
      }
    }
    L (i, 0, n) {
      g[i] = f[i] * iv[i];
    }
  }

  void Exp (mint *g, int n) {
    L (i, 1, n) {
      f[i] = 0;
      g[i] *= i;
    }
    f[0] = 1;
    L (i, 1, n) {
      L (j, 1, i) {
        f[i] += f[i - j] * g[j];
      }
      f[i] *= iv[i];
    }
    L (i, 0, n) {
      g[i] = f[i];
    }
  }

  vector<mint> mul (vector<mint> &f, const vector<mint> &g) {
    int n = siz(f), m = siz(g);
    vector<mint> h(n + m - 1);
    L (i, 0, n - 1) {
      if (f[i].v) {
        L (j, 0, m - 1) {
          h[i + j] += f[i] * g[j];
        }
      }
    }
    return h;
  }
}

using Poly::Ln;
using Poly::Exp;

mint ns[N], H[N][N], h[M][N], dp[M][N], f[N][N][N], g[N][N], T[N][M][N];

void DP (int n, int t) {
  int lim = n;
  if (t == 1) {
    lim = 1;
  }
  L (k, 1, lim) {
    L (c, k, n) {
      mint w = pw[c][c - k] * C[c - 1][k - 1] * ifc[c] * pq[c - k];
      L (i, 0, c) {
        f[k][c][i] = w * C[c][i];
      }
    }
  }
}

int main () {
  // freopen("1.out", "w", stdout);
  cin >> n >> q >> P;
  n = 59;
  // n = 60, q = 2, P = 998244353;
  bt = barrett(P);
  init();
  int pn = n / 2;
  search(pn);

  L (i, 1, n) {
    int sz = n / i;
    L (j, 0, sz) {
      H[i][j] = ifc[j].pow(i);
    }
    Ln(H[i], sz);
  }

  L (u, 1, tot) {
    auto &f = fx[u];
    L (i, 1, min(n, siz(f)) - 1) {
      if (f[i]) {
        L (j, 0, n / i) {
          h[u][j * i] += H[i][j] * f[i];
        }
      }
    }
    Exp(h[u], n);
    h[u][0] = 1;
    L (i, 1, n) {
      h[u][i] *= q;
    }
    Ln(h[u], n);
  }

  L (sz, 1, n - 1) {
    DP(n / sz, sz);
    L (t, 1, min(sz, pn)) {
      L (u, 1, tot) {
        if (!fx[u][t] && big[u] >= sz) {
          continue;
        }
        int z = fx[u][t];
        L (k, 0, z - 1) {
          mint cf = C[z][k] * sgn(z - k);
          int v = sp[u][t][k];
          L (i, len[u], n - len[u]) {
            dp[v][i] += dp[u][i] * cf;
          }
        }
      }
    }

    if (sz == 1) {
      L (a, 1, n) {
        L (b, 0, min(a, pn)) {
          dp[sp[1][1][b]][a] += f[1][a][b] * 2;
        }
      }
    } else {
      L (u, 1, tot) {
        if (big[u] >= sz) {
          continue;
        }
        int U = (n - len[u]) / sz;
        mint x = h[u][sz], s = 1;
        L (k, 1, U) {
          s *= x;
          L (i, k, U) {
            L (j, 0, min(i, U - i)) {
              g[i][j] += s * f[k][i][j];
            }
          }
        }
        L (a, 1, U) {
          L (b, 0, min(a, U - a)) {
            L (i, len[u], n - max(len[u], (a + b) * sz)) {
              T[b][u][i + a * sz] += dp[u][i] * g[a][b];
            }
          }
        }
        L (a, 1, U) {
          L (b, 0, min(a, U - a)) {
            g[a][b] = 0;
          }
        }
      }

      L (u, 1, tot) {
        if (big[u] < sz) {
          L (i, len[u], n - len[u]) {
            T[0][u][i] += dp[u][i];
            dp[u][i] = 0;
          }
        }
      }

      L (a, 0, n / sz / 2) { 
        R (t, min(pn, sz - 1), 1) {
          L (u, 1, tot) {
            if (big[u] >= sz || !fx[u][t]) {
              continue;
            }
            int z = fx[u][t];
            int sl = len[u] + a * sz, sr = a * sz;
            L (i, t + 1, min(pn, sz - 1)) {
              sr += fx[u][i] * i;
            }
            L (k, 0, z) {
              int ss = sr + k * t;
              if (k == z) {
                L (i, max(n - ss + 1, sl), n - sr) {
                  T[a][u][i] = 0;
                }
              } else {
                int v = sp[u][t][k];
                mint cf = C[z][k];
                L (i, sl, n - ss) {
                  T[a][v][i] += T[a][u][i] * cf;
                }
              }
            }
          }
        }

        L (u, 1, tot) {
          int ss = len[u] + a * sz;
          if (big[u] >= sz) {
            continue;
          }
          if (ss > pn) {
            break;
          }
          int v = u;
          if (a) {
            v = sp[u][sz][a];
          }
          L (i, ss, n - ss) {
            dp[v][i] += T[a][u][i];
            T[a][u][i] = 0;
          }
        }
      }
    }

    L (i, 1, n) {
      ns[i] += dp[1][i];
      dp[1][i] = 0;
    }
  }
  L (i, 1, n) {
    ns[i] *= fc[i - 1];
  }
  L (i, 1, n) {
    cout << ns[i].v << '\n';
  }
  L (i, 60, 100) {
    cout << 0 << '\n';
  }
  cerr << clock() << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2285ms
memory: 1485816kb

input:

100 910342260 935929297

output:

2
884755223
405748879
55307606
748696538
304834155
315697763
545849606
150856603
340166369
187291539
34335515
263202113
758718871
216403887
172000291
315342035
29014436
739189979
858970835
831719202
766115218
760340419
486004376
472284273
872493440
417345296
159771945
115754692
14041056
827964774
26...

result:

points 0.0 You got 0 pts!