QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448085#7647. 树哈希JWRuixi0 0ms0kbC++204.3kb2024-06-19 10:57:122024-06-19 10:57:13

Judging History

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

  • [2024-06-19 10:57:13]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-06-19 10:57:12]
  • 提交

answer

#ifdef LOCAL
#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;

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

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

mint A[N][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;
  }
  L (p, 1, n) {
    auto f = A[p];
    L (i, 0, n / p) {
      f[1][i] = ifc[i].pow(p);
    }
    L (c, 2, n / p) {
      L (i, 0, n / p) {
        L (j, 0, i) {
          f[c][i] += f[c - 1][j] * f[1][i - j];
        }
      }
    }
  }
}

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

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

int f[N];
mint g[N], h[N];

IL mint calc (int m) {
  if (m == 1) {
    return pq[f[1]] * pw[f[1]][f[1] - 1] * ifc[f[1]];
  }
  L (i, 1, m) {
    g[i] = 0;
  }
  g[0] = 1;
  L (p, 1, m - 1) {
    if (!f[p]) {
      continue;
    }
    L (i, 0, m) {
      h[i] = 0;
    }
    L (i, 0, m) {
      if (g[i].v) {
        L (j, 0, (m - i) / p) {
          h[i + j * p] += g[i] * A[p][f[p]][j];
        }
      }
    }
    L (i, 0, m) {
      g[i] = h[i];
    }
  }
  g[0] -= 1;
  L (i, 1, m) {
    g[i] *= q;
  }
  g[0] += 1;
  Ln(g, m);
  mint x = g[m], s = 1, ret = 0;
  L (k, 1, f[m] - 1) {
    s *= x;
    ret += s * pw[f[m]][f[m] - k - 1] * k * C[f[m]][k] * pq[f[m] - k];
  }
  ret += s * x;
  return ret * ifc[f[m]];
}

mint ns[N];

int a[N], tot, all;

void dfs (int i,  mint cur) {
  if (tot > 1 && a[tot] ^ a[tot - 1]) {
    cur *= calc(a[tot - 1]);
  }
  ns[all] += cur * calc(a[tot]);
  L (j, i, n - all) {
    ++f[a[++tot] = j];
    all += j;
    dfs(j, cur);
    all -= j;
    --f[a[tot--]];
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q >> P;
  int nn = n;
  n = min(n, 60);
  bt = barrett(P);
  init();
  f[1] = a[tot = 1] = all = 1;
  dfs(1, 1);
  L (i, 1, n) {
    ns[i] *= fc[i - 1];
    cout << ns[i].v << '\n';
  }
  L (i, n + 1, nn) {
    cout << "0\n";
  }
}
// I love WHQ!

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

100 910342260 935929297

output:


result: