QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#450600#7647. 树哈希JWRuixi100 ✓675ms157216kbC++2011.4kb2024-06-22 16:13:052024-06-22 16:13:05

Judging History

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

  • [2024-06-22 16:13:05]
  • 评测
  • 测评结果:100
  • 用时:675ms
  • 内存:157216kb
  • [2024-06-22 16:13:05]
  • 提交

answer

#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 B = 3;
constexpr int M = 3000;
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];
    }
  }

  void 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];
        }
      }
    }
    f = h;
  }
}

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

namespace ez {
  vector<vi> F[N];
  vi t[N], e[N];
  int sz[N], s[N], ct;
  mint dv[N], vl[N];

  map<vector<pair<int, int>>, mint> bfs (int n) {
    F[0].eb(vi{});
    L (i, 1, n) {
      for (auto &v : F[i - 1]) {
        ++ct;
        e[ct] = v;
        sz[ct] = i;
        t[i].eb(ct);
        dv[ct] = 1;
        s[ct] = 1 << (ct - 1);
        int p = 0;
        L (j, 0, siz(v) - 1) {
          s[ct] |= s[v[j]];
          if (j && v[j] != v[j - 1]) {
            p = 0;
          }
          dv[ct] *= dv[v[j]] * (++p);
        }
        L (j, 0, n - i) {
          for (auto &o : F[j]) {
            auto nv = o;
            nv.eb(ct);
            F[i + j].eb(nv);
          }
        }
      }
    }
    L (i, 1, ct) {
      vl[i] = (LL)qpow(q, i) * qpow(P + 1 - q, ct - i) % P;
    }
    map<vector<pair<int, int>>, mint> mp;
    L (S, 1, (1 << ct) - 1) {
      vector<pair<int, int>> v;
      L (i, 1, ct) {
        if ((s[i] & S) == s[i]) {
          v.eb(sz[i], dv[i].v);
        }
      }
      if (siz(v)) {
        mp[v] += vl[__builtin_popcount(S)];
      }
    }
    return mp;
  }

  vector<mint> calc (int n) {
    vector<mint> ret(n + 1);
    L (i, 1, n) {
      for (int u : t[i]) {
        ret[i] += pq[__builtin_popcount(s[u])] * fc[i - 1] * dv[u].inv();
      }
    }
    return ret;
  }
}

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, vector<pair<int, int>> v) {
  int lim = n / (B + 1);
  if (t == 1) {
    lim = 1;
  }
  vector<mint> it{1};
  for (auto [sz, dv] : v) {
    vector<mint> th(n + 1);
    dv = qpow(dv);
    L (i, 0, n / sz) {
      th[i * sz] = ifc[i].pow(t) * qpow(dv, i * t);
    }
    mul(it, th), it.resize(n + 1);
  }
  auto nit = it;
  nit.resize(B);

  vector<vector<mint>> p1(n + 1), p2(n + 1);
  p1[0].resize(n + 1);
  p2[0].resize(n + 1);
  p1[0][0] = p2[0][0] = 1;
  L (i, 1, n) {
    p1[i] = p1[i - 1];
    mul(p1[i], it);
    p1[i].resize(n + 1);
    p2[i] = p2[i - 1];
    mul(p2[i], nit);
    p2[i].resize(n + 1);
  }

  L (k, 1, lim) {
    vector f(n + 1, vector<mint>(n + 1));
    L (c, k, n) {
      L (s, 0, c) {
        f[s][c - s] = mint(s).pow(c - k) * C[c - 1][k - 1] * C[c][s] * ifc[c] * pq[c - k];
      }
    }
    L (i, 0, n) {
      vector<mint> g(n + 1);
      L (j, 0, n - i) {
        f[i][j] *= sgn(j);
        L (k, 0, n - i - j) {
          g[j + k] += f[i][j] * p2[j][k];
        }
      }
      L (j, 0, n - i) {
        f[i][j] = g[j];
      }
      g.assign(n + 1, 0);
      L (j, 0, n - i) {
        g[i + j] = p1[i][j];
      }
      mul(f[i], g), f[i].resize(n + 1);
    }
    L (i, 0, n) {
      L (j, 0, i - 1) {
        L (k, i, n) {
          f[j][k] += f[i][k] * C[i][j];
        }
      }
    }
    L (i, k, n) {
      L (j, 0, i) {
        ::f[k][i][j] = f[j][i];
      }
    }
  }
}

int main () {
  cin >> n >> q >> P;
  // n = 100, q = 2, P = 998244353;
  bt = barrett(P);
  init();
  int pn = n / (B + 2);
  search(pn);

  auto mp = ez::bfs(B);
  auto ret = ez::calc(B);

  if (n <= B) {
    L (i, 1, n) {
      cout << ret[i].v << '\n';
    }
    return 0;
  }

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

  for (auto [S, Z] : mp) {
    L (u, 1, tot) {
      L (i, 0, n) {
        dp[u][i] = 0;
      }
    }
    L (sz, 1, (n - 1) / (B + 1)) {
      DP(n / sz, sz, S);
      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] * (B + 1)) {
              dp[v][i] += dp[u][i] * cf;
            }
          }
        }
      }

      if (sz == 1) {
        Z *= q;
        L (a, 1, n) {
          L (b, 0, min(a, pn)) {
            dp[sp[1][1][b]][a] += f[1][a][b] * Z;
          }
        }
      } 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) {
              int pp = min(i, (U - i) / (B + 1));
              L (j, 0, pp) {
                g[i][j] += s * f[k][i][j];
              }
            }
          }
          L (a, 1, U) {
            int pp = min(a, (U - a) / (B + 1));
            L (b, 0, pp) {
              L (i, len[u], n - max(len[u] * (B + 1), a * sz + b * (B + 1) * sz)) {
                T[b][u][i + a * sz] += dp[u][i] * g[a][b];
              }
            }
          }
          L (a, 1, U) {
            int pp = min(a, (U - 1) / (B + 1));
            L (b, 0, pp) {
              g[a][b] = 0;
            }
          }
        }

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

        L (a, 0, n / sz / (B + 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 * (B + 1);
              L (i, t + 1, min(pn, sz - 1)) {
                sr += fx[u][i] * i * (B + 1);
              }
              L (k, 0, z) {
                int ss = sr + k * t * (B + 1);
                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 * (B + 1)) {
              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, B) {
    ns[i] = ret[i];
  }
  L (i, 1, n) {
    cout << ns[i].v << '\n';
  }
}
// I love WHQ!

詳細信息

Subtask #1:

score: 100
Accepted

Test #1:

score: 100
Accepted
time: 673ms
memory: 156996kb

input:

100 910342260 935929297

output:

910342260
816177711
569226551
514707635
267406725
391906453
250727611
208481307
81485772
23235693
216730633
285646992
175230876
274553119
174038157
203318484
775234565
322891510
933522659
900692754
745314049
700055439
779013783
855717291
855228480
586396378
894281940
384312444
837857031
272136268
26...

result:

ok Correct!

Test #2:

score: 100
Accepted
time: 668ms
memory: 157216kb

input:

100 222959056 947643239

output:

222959056
358599927
365062242
287299555
872152310
785181552
689517811
751458049
373969559
887125628
238000283
265869067
862846962
717459206
118380127
903859172
38731072
220551290
311944377
678478487
757437607
696077670
937732236
530238679
704937150
7448691
641846446
371506084
393996598
847615147
228...

result:

ok Correct!

Test #3:

score: 100
Accepted
time: 675ms
memory: 156740kb

input:

100 135352674 235854343

output:

135352674
116843515
129198122
128256418
202034449
101078108
134511179
26177395
38146936
177689345
171471260
220203615
2725266
54489245
202150371
51581049
9159057
174134120
214954721
6858381
164936156
136507834
11983036
56210425
230637079
37588391
129846550
182944624
160550968
143284554
172157415
229...

result:

ok Correct!

Test #4:

score: 100
Accepted
time: 667ms
memory: 156712kb

input:

100 538608644 566215339

output:

538608644
365236991
134179965
39370099
416828003
17910602
226317362
529379896
407121368
81806097
249408176
336758120
296361261
35236747
429449088
328368699
409154256
418665686
24463075
203118458
352974481
3351773
506522141
61405204
248921056
351694297
485859431
419342548
150905111
157365902
53232656...

result:

ok Correct!

Test #5:

score: 100
Accepted
time: 672ms
memory: 156744kb

input:

100 56831820 281897771

output:

56831820
213573518
5338712
114481529
104176011
222091299
258318286
168492731
248042852
279768543
163273831
250332871
125456436
55441194
94771937
85241933
265069860
227132810
189427807
26222782
184487649
201740742
267160664
98981147
101908728
84191074
210184730
48919201
18122051
176229976
226118070
1...

result:

ok Correct!