QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235514#7647. 树哈希hos_lyric#8 1667ms4164kbC++147.1kb2023-11-02 21:02:052024-07-04 02:51:00

Judging History

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

  • [2024-07-04 02:51:00]
  • 评测
  • 测评结果:8
  • 用时:1667ms
  • 内存:4164kb
  • [2023-11-02 21:02:05]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
// Barrett
struct ModInt {
  static unsigned M;
  static unsigned long long NEG_INV_M;
  static void setM(unsigned m) { M = m; NEG_INV_M = -1ULL / M; }
  unsigned x;
  ModInt() : x(0U) {}
  ModInt(unsigned x_) : x(x_ % M) {}
  ModInt(unsigned long long x_) : x(x_ % M) {}
  ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) {
    const unsigned long long y = static_cast<unsigned long long>(x) * a.x;
    const unsigned long long q = static_cast<unsigned long long>((static_cast<unsigned __int128>(NEG_INV_M) * y) >> 64);
    const unsigned long long r = y - M * q;
    x = r - M * (r >= M);
    return *this;
  }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
unsigned ModInt::M;
unsigned long long ModInt::NEG_INV_M;
// !!!Use ModInt::setM!!!
////////////////////////////////////////////////////////////////////////////////

using Mint = ModInt;

constexpr int LIM_INV = 1010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}


int N;
Mint Q;
int MO;

Mint ans[110];

Mint forest[110][110];
Mint S2[110][110];

/*
  each part: isomorphic subtrees
  ps: incr.
  in-tree: large part to small part
  parts of same size: ban cycle
*/
int ps[110];
void check(int sum, int len) {
// cerr<<"[check] "<<1+sum<<"; ";pv(ps,ps+len);
  Mint pie = Q.pow(1 + len);
  Mint lab = fac[sum];
  Mint way = 1;
  for (int i = 0; i < len; ++i) {
    Mint here = 0;
    for (int k = ps[i]; --k >= 0; ) {
// cerr<<"    HELP "<<ps[i]<<" "<<k<<": "<<(((k&1)?-1:+1) * fac[k] * S2[ps[i]][k + 1])<<endl;
      (here *= Q) += ((k&1)?-1:+1) * fac[k] * S2[ps[i]][k + 1];
    }
    pie *= here;
  }
  for (int i = 0, j = 0; i < len; i = j) {
    for (; j < len && ps[i] == ps[j]; ++j) {}
    lab *= invFac[ps[i]].pow(j - i);
    lab *= invFac[j - i];
    const int n = ps[i] * (j - i);
    // root
    vector<Mint> crt(n + 1, 1);
    for (int k = 0; k < i; ++k) {
      auto nxt = crt;
      for (int m = 0; m <= n; ++m) {
        for (int l = 1; ps[k] * l <= m; ++l) {
          nxt[m] += crt[m - ps[k] * l] * fac[m] * invFac[m - ps[k] * l] * invFac[l].pow(ps[k]);
        }
      }
      crt.swap(nxt);
    }
    Mint here = 0;
    for (int k = 1; k <= j - i; ++k) {
      here += fac[ps[i]].pow((j - i) - k) * forest[j - i][k] * crt[ps[i] * k];
    }
    way *= here;
  }
// cerr<<"  pie = "<<pie<<", lab = "<<lab<<", way = "<<way<<endl;
  ans[1 + sum] += pie * lab * way;
}

void dfs(int pos, int limSum, int sum, int last) {
  check(sum, pos);
  for (int &p = ps[pos] = last; sum + p <= limSum; ++p) {
    dfs(pos + 1, limSum, sum + p, p);
  }
}

int main() {
  for (; ~scanf("%d%u%d", &N, &Q.x, &MO); ) {
    Mint::setM(MO);
    prepare();
    
    for (int n = 1; n <= N; ++n) {
      for (int k = 1; k <= n; ++k) {
        forest[n][k] = binom(n - 1, k - 1) * Mint(n).pow(n - k);
      }
// cerr<<"forest["<<n<<"] = ";pv(forest[n],forest[n]+n+1);
    }
    for (int n = 0; n <= N; ++n) {
      S2[n][0] = 0;
      S2[n][n] = 1;
      for (int k = 1; k < n; ++k) {
        S2[n][k] = S2[n - 1][k - 1] + k * S2[n - 1][k];
      }
    }
    
    memset(ans, 0, sizeof(ans));
    dfs(0, min(N - 1, 40), 0, 1);
    
    for (int n = 1; n <= N; ++n) {
      printf("%u\n", ans[n].x);
    }
  }
  return 0;
}

详细

Subtask #1:

score: 8
Acceptable Answer

Test #1:

score: 8
Acceptable Answer
time: 1656ms
memory: 3876kb

input:

100 910342260 935929297

output:

910342260
816177711
569226551
514707635
537579012
54225031
926399351
528641717
865870143
268023658
432929781
115276615
156062649
411948005
567155032
387524375
917068828
25805775
879317375
133148896
791250262
407496628
498252206
604801513
916010864
500037249
436769409
191154496
431303105
679237869
56...

result:

points 0.080 You got 8 pts!

Test #2:

score: 8
Acceptable Answer
time: 1655ms
memory: 3872kb

input:

100 222959056 947643239

output:

222959056
358599927
365062242
287299555
819327639
393519079
770225811
704895562
397518189
909341167
406797911
31861163
506834456
725104755
172158352
406385484
302970429
139567080
445409368
581435816
512747294
139053952
197720828
91928044
669689793
650729421
532386912
897530251
261894131
327969880
11...

result:

points 0.080 You got 8 pts!

Test #3:

score: 8
Acceptable Answer
time: 1654ms
memory: 3876kb

input:

100 135352674 235854343

output:

135352674
116843515
129198122
128256418
76582131
37722704
67549464
214373919
18812100
230562395
125405609
24544517
232553642
69455097
37461626
38692257
164148247
128437450
85987582
51036497
56870557
81544820
99296039
203791229
89845223
86099326
123998890
66727889
216496153
209167906
216576624
379909...

result:

points 0.080 You got 8 pts!

Test #4:

score: 8
Acceptable Answer
time: 1655ms
memory: 4164kb

input:

100 538608644 566215339

output:

538608644
365236991
134179965
39370099
20827050
199108637
158573653
356345209
526868399
471863508
423384183
45887513
552279064
329233505
314235311
263997297
343125173
182627423
54952695
152920417
410840553
301360187
360557878
193719269
318672908
471366803
185870276
191766490
172044723
120571914
2230...

result:

points 0.080 You got 8 pts!

Test #5:

score: 8
Acceptable Answer
time: 1667ms
memory: 4164kb

input:

100 56831820 281897771

output:

56831820
213573518
5338712
114481529
71692760
3716510
143883481
12197797
36552006
209493937
37038852
164733903
178719810
10425101
105386296
46898175
10966914
23502575
2478820
224441357
170494454
149993590
178365336
103226718
203283189
146943507
252461441
84732213
196976326
166707443
164738221
173019...

result:

points 0.080 You got 8 pts!