QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235514 | #7647. 树哈希 | hos_lyric# | 8 | 1667ms | 4164kb | C++14 | 7.1kb | 2023-11-02 21:02:05 | 2024-07-04 02:51:00 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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!