QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473538#7647. 树哈希hos_lyric48 1442ms28624kbC++149.2kb2024-07-12 08:46:402024-07-12 08:46:41

Judging History

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

  • [2024-07-12 08:46:41]
  • 评测
  • 测评结果:48
  • 用时:1442ms
  • 内存:28624kb
  • [2024-07-12 08:46:40]
  • 提交

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


constexpr int N = 50;

int NN, MO;
Mint q;

// h(x) = log(1 + q (g(x) - 1))
void pie(int deg, const Mint *gs, Mint *hs) {
  static Mint work[N + 1];
  work[0] = 1;
  for (int i = 1; i <= deg; ++i) work[i] = q * gs[i];
  for (int i = 1; i <= deg; ++i) {
    hs[i] = i * work[i];
    for (int j = 1; j < i; ++j) hs[i] -= work[i - j] * hs[j];
  }
  for (int i = 1; i <= deg; ++i) hs[i] *= inv[i];
}

// partition of <= N/2
// (0, fs[1], ..., fs[N/2])
int U;
vector<int> sums;
vector<vector<int>> fss;
vector<vector<vector<int>>> sub, sup;

int indexOf(const vector<int> &fs) {
  auto it = lower_bound(fss.begin(), fss.end(), fs);
  assert(it != fss.end());
  assert(*it == fs);
  return it - fss.begin();
}

void dfs(int n, int a, vector<int> &fs) {
  if (a == N/2) {
    sums.push_back(n);
    fss.push_back(fs);
    return;
  }
  ++a;
  const int lim = (N/2 - n) / a;
  for (int f = 0; f <= lim; ++f) {
    fs[a] = f;
    dfs(n + f * a, a, fs);
  }
  fs[a] = 0;
}

int main() {
  scanf("%d%u%d", &NN, &q.x, &MO);
  Mint::setM(MO);
  prepare();
  
  {
    vector<int> fs(N/2 + 1, 0);
    dfs(0, 0, fs);
  }
  U = fss.size();
  sub.assign(U, vector<vector<int>>(N/2 + 1));
  sup.assign(U, vector<vector<int>>(N/2 + 1));
  for (int u = 0; u < U; ++u) {
    auto fs = fss[u];
    for (int a = 1; a <= N/2; ++a) {
      if (fss[u][a]) {
        sub[u][a].resize(fss[u][a]);
        for (int f = 0; f < fss[u][a]; ++f) {
          fs[a] = f;
          sub[u][a][f] = indexOf(fs);
        }
      } else {
        const int lim = (N/2 - sums[u]) / a;
        sup[u][a].resize(lim + 1);
        for (int f = 0; f <= lim; ++f) {
          fs[a] = f;
          sup[u][a][f] = indexOf(fs);
        }
      }
      fs[a] = fss[u][a];
    }
  }
  
  vector<vector<Mint>> G(U), H(U);
  for (int u = 0; u < U; ++u) {
    const int deg = N - sums[u];
    G[u].assign(deg + 1, 0);
    H[u].assign(deg + 1, 0);
    if (u == 0) {
      G[u][0] = 1;
    } else {
      for (int a = N/2; ; --a) if (fss[u][a]) {
        const int v = sub[u][a].back();
        for (int j = 0; j * a <= deg; ++j) {
          const Mint t = invFac[j].pow(a);
          for (int i = 0; i + j * a <= deg; ++i) {
            G[u][i + j * a] += G[v][i] * t;
          }
        }
        break;
      }
    }
    pie(deg, G[u].data(), H[u].data());
// cerr<<"u="<<u<<" sums[u]="<<sums[u]<<" fss[u]="<<fss[u]<<" sub[u]="<<sub[u]<<" sup[u]="<<sup[u]<<" G[u]="<<G[u]<<" H[u]="<<H[u]<<endl;
  }
  
  /*
    dp[n][u]
      n: # vertex
      u: partition, attach >= 1 child later
      n <= |u| <= N - n
  */
  vector<vector<Mint>> dp(N + 1, vector<Mint>(U, 0));
  dp[0][0] = 1;
  for (int a = 1; a <= N; ++a) {
    auto trans = [&](int sig) -> void {
      for (int n = 0; n <= N; ++n) {
        for (int b = 1; b <= N/2 && b < a; ++b) {
          for (int u = 0; u < U; ++u) if (dp[n][u]) {
            const int f = fss[u][b];
            for (int ff = 0; ff < f; ++ff) {
              const int v = sub[u][b][ff];
              dp[n][v] += dp[n][u] * ((f-ff)&1?sig:+1) * binom(f, ff);
            }
          }
        }
      }
    };
    trans(-1);
// cerr<<__LINE__<<": a = "<<a<<", dp = "<<dp<<endl;
    for (int n = N; n >= 0; --n) {
      for (int u = 0; u < U; ++u) if (dp[n][u]) {  // TODO
        for (int f = 1; n + f * a <= N; ++f) {
          const Mint val = (a == 1) ? (invFac[f] * Mint(f).pow(f - 1) * q.pow(f)) : (invFac[f] * H[u][a] * (H[u][a] + q * f).pow(f - 1));
          const int lim = min((N/2 - sums[u]) / a, f);
          for (int ff = 0; ff <= lim; ++ff) {  // TODO
            const int v = ff ? sup[u][a][ff] : u;
            dp[n + f * a][v] += dp[n][u] * val * binom(f, ff);
          }
        }
      }
    }
// cerr<<__LINE__<<": a = "<<a<<", dp = "<<dp<<endl;
    trans(+1);
// cerr<<__LINE__<<": a = "<<a<<", dp = "<<dp<<endl;
    for (int n = 0; n < N; ++n) {
      for (int u = 0; u < U; ++u) if (n + sums[u] > N) {
        dp[n][u] = 0;
      }
    }
  }
  
  vector<Mint> ans(N + 1);
  for (int n = 0; n <= N; ++n) {
    ans[n] = dp[n][0];
  }
  
  // EGF -> fixed root
  for (int n = 1; n <= N; ++n) {
    ans[n] *= fac[n - 1];
  }
  ans.resize(NN + 1, 0);
  for (int n = 1; n <= NN; ++n) {
    printf("%u\n", ans[n].x);
  }
  return 0;
}
/*
10 10 1000000007

10
100
2100
69100
3040100
168335100
222076023
63944968
21587160
844588529
*/

详细

Subtask #1:

score: 48
Acceptable Answer

Test #1:

score: 48
Acceptable Answer
time: 1412ms
memory: 28624kb

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
13774937
289289189
350...

result:

points 0.480 You got 48 pts!

Test #2:

score: 48
Acceptable Answer
time: 1442ms
memory: 28612kb

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
447810391
783651844
625...

result:

points 0.480 You got 48 pts!

Test #3:

score: 48
Acceptable Answer
time: 1439ms
memory: 28504kb

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
119805049
221591404
162552601
186...

result:

points 0.480 You got 48 pts!

Test #4:

score: 48
Acceptable Answer
time: 1431ms
memory: 28580kb

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
146415751
178371945
27124423...

result:

points 0.480 You got 48 pts!

Test #5:

score: 48
Acceptable Answer
time: 1429ms
memory: 28616kb

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
13655254
229320762
238370870
2...

result:

points 0.480 You got 48 pts!