Overall
Bronze
B1
#include <bits>
using namespace std;
char s[100020];
int n;
int main()
{
freopen("socdist1.in", "r", stdin);
freopen("socdist1.out", "w", stdout);
scanf("%d", &n);
scanf("%s", s);
int prev = -1;
vector<int> d;
int first = -1;
int last = -1;
int cowcnt = 0;
for (int i = 0; i < n; i++) { if (s[i] == '1') { cowcnt++; if (first == -1) { first = i + 1; } last = n - i; if (prev != -1) { d.push_back(i - prev); } prev = i; } } int ans = 0; if (cowcnt == 0) { ans = n - 1; } else if (cowcnt == 1) { ans = max(ans, (first - 1) / 2); ans = max(ans, (last - 1) / 2); ans = max(ans, min(first - 1, last - 1)); } else { sort(d.begin(), d.end()); ans = max(ans, min(d[0], min(first - 1, last - 1))); ans = max(ans, min(min(d[0], first - 1), d.back() / 2)); ans = max(ans, min(min(d[0], last - 1), d.back() / 2)); if (cowcnt >= 2)
{
ans = max(ans, min(d[0], d.back() / 3));
}
if (cowcnt >= 3)
{
ans = max(ans, min(d[0], d[d.size() - 2] / 2));
}
}
printf("%d\n", ans);
return 0;
}
```</int></bits>
## B2
```cpp
#include <bits>
using namespace std;
pair<int int> a[100020];
int main()
{
freopen("socdist2.in", "r", stdin);
freopen("socdist2.out", "w", stdout);
int n;
cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second;
}
sort(a, a + n);
int d = 1e9;
for (int i = 1; i < n; i++)
{
if (a[i].second + a[i - 1].second == 1)
{
d = min(d, a[i].first - a[i - 1].first);
}
}
int ans = 0;
for (int i = 0; i < n; i++) { if (a[i].second) { if (i == 0 || a[i - 1].second == 0 || a[i].first - a[i-1].first >= d)
{
ans++;
}
}
}
printf("%d\n", ans);
return 0;
}
```</int></bits>
## B3
```cpp
#include <bits>
using namespace std;
int n, m;
char s[120];
char c[120];
int d[120];
pair<int pair int> > a[260];
bool check(int root, int times)
{
for (int i = 0; i < n; i++)
{
c[i] = '0';
d[i] = times;
}
c[root] = '1';
for (int i = 0; i < m; i++) { if (c[a[i].second.first] == '0' && c[a[i].second.second] == '0') { } else if (c[a[i].second.first] == '0' && c[a[i].second.second] == '1') { if (d[a[i].second.second] > 0)
{
d[a[i].second.second]--;
c[a[i].second.first] = '1';
}
}
else if (c[a[i].second.first] == '1' && c[a[i].second.second] == '0')
{
if (d[a[i].second.first] > 0)
{
d[a[i].second.first]--;
c[a[i].second.second] = '1';
}
}
else if (c[a[i].second.first] == '1' && c[a[i].second.second] == '1')
{
if (d[a[i].second.first] > 0)
{
d[a[i].second.first]--;
}
if (d[a[i].second.second] > 0)
{
d[a[i].second.second]--;
}
}
}
return strcmp(s, c) == 0;
}
int main()
{
freopen("tracing.in", "r", stdin);
freopen("tracing.out", "w", stdout);
scanf("%d%d", &n, &m);
scanf("%s", s);
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
a[i].second.first--;
a[i].second.second--;
}
sort(a, a + m);
int rootcnt = 0;
int mink = m + 1;
int maxk = 0;
for (int i = 0; i < n; i++)
{
bool cani = false;
for (int k = 0; k <= m + 1; k++)
{
if (check(i, k))
{
mink = min(mink, k);
maxk = max(maxk, k);
cani = true;
}
}
if (cani)
{
rootcnt++;
}
}
printf("%d %d ", rootcnt, mink);
if (maxk != m + 1)
{
printf("%d\n", maxk);
}
else
{
printf("Infinity\n");
}
return 0;
}
```</int></bits>
## S1
```cpp
#include <bits>
using namespace std;
int n, m;
pair<long long> a[100020];
bool check(long long d)
{
int cnt = 0;
long long s = a[0].first;
int i = 0;
while (true)
{
if (a[i].first <= s && s <= a[i].second) { cnt++; if (cnt >= m)
{
return true;
}
s += d;
}
while (i < n && s > a[i].second)
{
i++;
}
if (i == n)
{
break;
}
if (s < a[i].first) { s = a[i].first; } } return cnt >= m;
}
int main()
{
freopen("socdist.in", "r", stdin);
freopen("socdist.out", "w", stdout);
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++)
{
scanf("%lld%lld", &a[i].first, &a[i].second);
}
sort(a, a + n);
long long L = 0;
long long R = 1e18 + 1;
while (L < R - 1)
{
long long M = (L + R) / 2;
if (check(M))
{
L = M;
}
else
{
R = M;
}
}
printf("%lld\n", L);
return 0;
}
```</long></bits>
## S2
```cpp
#include <bits>
using namespace std;
int n, m;
int a[100020][2];
int z[100020];
int v[100020];
int main()
{
freopen("cereal.in", "r", stdin);
freopen("cereal.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) { cin >> a[i][0] >> a[i][1];
}
for (int i = n; i > 0; i--)
{
int j = i;
z[i] = z[i + 1];
while (true)
{
if (v[a[j][0]] == 0)
{
v[a[j][0]] = j;
z[i]++;
break;
}
else if (v[a[j][0]] > j)
{
int nj = v[a[j][0]];
v[a[j][0]] = j;
j = nj;
}
else if (v[a[j][1]] == 0)
{
v[a[j][1]] = j;
z[i]++;
break;
}
else if (v[a[j][1]] > j)
{
int nj = v[a[j][1]];
v[a[j][1]] = j;
j = nj;
}
else
{
break;
}
}
}
for (int i = 1; i <= n; i++)
{
printf("%d\n", z[i]);
}
return 0;
}
```</bits>
## S3
```cpp
#include <bits>
using namespace std;
int n;
int x[100020];
int y[100020];
int r1[100020];
int r2[100020];
int q[100020];
int p[100020];
bool cmp1(int a, int b)
{
return x[a] < x[b] || (x[a] == x[b] && y[a] < y[b]); } bool cmp2(int a, int b) { return y[a] > y[b] || (y[a] == y[b] && x[a] > x[b]);
}
int main()
{
freopen("moop.in", "r", stdin);
freopen("moop.out", "w", stdout);
cin >> n;
for (int i = 0; i < n; i++) { cin >> x[i] >> y[i];
r1[i] = i;
r2[i] = i;
}
sort(r1, r1 + n, cmp1);
sort(r2, r2 + n, cmp2);
// for (int i = 0; i < n; i++)
// {
// printf("%d ", r1[i]);
// }
// printf("\n");
// for (int i = 0; i < n; i++)
// {
// printf("%d ", r2[i]);
// }
// printf("\n");
for (int i = 0; i < n; i++)
{
q[r1[i]] = i;
}
for (int i = 0; i < n; i++)
{
p[i] = q[r2[i]];
}
// for (int i = 0; i < n; i++)
// {
// printf("%d ", p[i]);
// }
// printf("\n");
int mx = 0;
int ans = 0;
for (int i = 0; i < n; i++)
{
mx = max(mx, p[i]);
if (mx == i)
{
ans++;
}
}
printf("%d\n", ans);
return 0;
}
```</bits>
## G1
```cpp
#include <bits>
using namespace std;
int n;
int c[100020];
void change(int x, int y)
{
for (x++; x <= n + 1; x += x & -x) { c[x] += y; } } int query(int x) { int re = 0; for (x++; x > 0; x -= x & -x)
{
re += c[x];
}
return re;
}
long long z[100020];
int main()
{
freopen("haircut.in", "r", stdin);
freopen("haircut.out", "w", stdout);
cin >> n;
for (int i = 0; i < n; i++) { int x; cin >> x;
int u = i - query(x);
z[x] -= u;
z[n] += u;
change(x, 1);
}
for (int i = n - 1; i >= 0; i--)
{
z[i] += z[i + 1];
}
for (int i = 0; i < n; i++)
{
printf("%lld\n", z[i]);
}
return 0;
}
```</bits>
## G2
```cpp
#include <bits>
using namespace std;
int n, m;
int f[200020];
int c[200020], cc;
vector<int> a[200020];
set<int> q;
int F(int x)
{
return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
x = F(x);
y = F(y);
if (x == y)
{
return;
}
if (x > y)
{
swap(x, y);
}
f[y] = x;
if (a[x].size() < a[y].size())
{
a[x].swap(a[y]);
}
for (int i: a[y])
{
a[x].push_back(F(i));
}
a[y].clear();
}
int main()
{
freopen("fcolor.in", "r", stdin);
freopen("fcolor.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &y, &x);
a[y].push_back(x);
}
for (int i = 1; i <= n; i++) { f[i] = i; if (a[i].size() > 1)
{
q.insert(i);
}
}
while (q.size())
{
int u = *q.begin();
u = F(u);
q.erase(q.begin());
for (int i = 0; i < a[u].size(); i++) { a[u][i] = F(a[u][i]); } sort(a[u].begin(), a[u].end()); a[u].resize(unique(a[u].begin(), a[u].end()) - a[u].begin()); if (a[u].size() > 0)
{
int base = a[u][0];
for (int i = 1; i < a[u].size(); i++) { U(base, a[u][i]); } base = F(base); if (a[base].size() > 1)
{
q.insert(base);
}
}
}
for (int i = 1; i <= n; i++)
{
if (c[F(i)] == 0)
{
c[F(i)] = ++cc;
}
printf("%d\n", c[F(i)]);
}
return 0;
}
```</int></int></bits>
## G3
```cpp
#include <bits>
using namespace std;
typedef long long ll;
int n, mod;
int p[10020], pc;
int isPrime(int x)
{
if (x < 2)
{
return false;
}
for (int i = 2; i * i <= x; i++) { if (x % i == 0) { return false; } } return true; } ll f[10020]; int main() { freopen("exercise.in", "r", stdin); freopen("exercise.out", "w", stdout); cin >> n >> mod;
for (int i = 1; i <= n; i++)
{
if (isPrime(i))
{
p[pc++] = i;
}
}
for (int i = 0; i <= n; i++)
{
f[i] = 1;
}
for (int i = 0; i < pc; i++) { for (int j = n; j > 0; j--)
{
for (int k = p[i]; k <= j; k *= p[i])
{
f[j] = (f[j] + f[j - k] * k) % mod;
}
}
}
printf("%lld\n", f[n]);
return 0;
}
```</bits>
## P1
```cpp
#include <bits>
using namespace std;
const int mod = 1000000007;
const int inv2 = 500000004;
int n;
int f[2020][2020]; // (i, j - 1) -> (i, j)
int g[2020][2020]; // (i - 1, j) -> (i, j)
char s[2020][2020];</bits>
int main()
{
freopen("sprinklers2.in", "r", stdin);
freopen("sprinklers2.out", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", s[i]);
}
for (int i = 1; i <= n; i++)
{
f[0][i] = 1;
g[i][0] = 1;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
f[i][j] = f[i][j-1];
if (s[i-1][j-1] != 'W')
{
f[i][j] = (f[i][j] + (long long)g[i][j-1] * inv2) % mod;
}
g[i][j] = g[i-1][j];
if (s[i-1][j-1] != 'W')
{
g[i][j] = (g[i][j] + (long long)f[i-1][j] * inv2) % mod;
}
}
}
int ans = (f[n][n] + g[n][n]) % mod;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (s[i][j] == '.')
{
ans = ans * 2 % mod;
}
}
}
printf("%d\n", ans);
return 0;
}
P2
#include <bits>
using namespace std;
typedef long long ll;
int n, mod, modd;
ll fac[7520];
ll inv[7520];
ll invfac[7520];
int p[1000], pc;
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {} ull reduce(ull a) { ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b return r >= b ? r - b : r;
}
}FM(2), FMD(2);
int isPrime(int x)
{
if (x < 2)
{
return false;
}
for (int i = 2; i * i <= x; i++) { if (x % i == 0) { return false; } } return true; } ll pw(ll x, ll y, ll mod) { ll re = 1; for (; y > 0; y >>= 1)
{
if (y & 1)
{
re = (re * x) % mod;
}
x = x * x % mod;
}
return re;
}
ll gcd(ll x, ll y)
{
return y ? gcd(y, x % y) : x;
}
ll lcm(ll x, ll y)
{
return x / gcd(x, y) * y;
}
ll P(int n, int m)
{
assert(0 <= m && m <= n);
return fac[n] * invfac[n - m] % mod;
}
int a[20];
int b[20];
long long gao0ans = 1;</bits>
// n x y
// n! / (n - x*y)! / pow(x, y) / y!
// C(n, x*y) * (x*y)! / pow(x, y) / y!
// G(n, x, y) =
int d1[7520];
int d2[7520];
unsigned c[7520][7520];
vector<unsigned> cc[7520];
// c[i][j] = c[i-1][j] + c[i-1][j-1]
map<pair int>, int> C[7520];
ll timecount = 0;
inline ll calc(int n, int x, int y)
{
timecount++;
return FMD.reduce((ull)c[n][x * y] * cc[x][y]);
pair<int int> u = make_pair(x, y);
if (C[n].find(u) != C[n].end())
{
return C[n][u];
}
// ll ret = c[n][x * y];
// for (int i = 1; i <= x * y; i++)
// {
// ret = ret * i;
// assert(ret < 1e60);
// }
// for (int i = 1; i <= y; i++)
// {
// ret = ret / x;
// ret = ret / i;
// }</int></pair></unsigned>
for (int i = 1; i <= y; i++)
{
d1[i] = x;
d2[i] = i;
}
ll re = c[n][x * y];
for (int i = 1; i <= x * y; i++)
{
int k = i;
for (int j = 1; j <= y; j++)
{
ll g;
g = gcd(k, d1[j]);
k /= g;
d1[j] /= g;
g = gcd(k, d2[j]);
k /= g;
d2[j] /= g;
if (k == 1)
{
break;
}
}
re = re * k % modd;
}
// ret %= modd;
// if (re != ret)
// {
// cout << n << ' ' << x << ' ' << y << ' ' << ret << ' ' << re << endl;
// }
// assert(re == ret);
C[n][u] = re;
// cout << n << ' ' << x << ' ' << y << ' ' << re << endl;
assert((long long)c[n][x * y] * cc[x][y] % modd == re);
return re;
}
void dfs(int x, int y, int z)
{
if (x == 0)
{
int l = 1;
ll sum = 1;
int cnt = 0;
for (int i = 0; i < z; i++)
{
l = lcm(l, a[i]);
cnt += a[i] * b[i];
sum = sum * calc(cnt, a[i], b[i]) % modd;
}
gao0ans = gao0ans * pw(l, sum, mod) % mod;
// for (int i = 0; i < z; i++)
// {
// printf("%d %d\n", a[i], b[i]);
// }
// printf("%lld %d\n", sum, cnt);
// printf("------\n");
return;
}
if (y == 0)
{
return;
}
dfs(x, y - 1, z);
a[z] = y;
for (b[z] = 1; b[z] * y <= x; b[z]++)
{
dfs(x - b[z] * y, y - 1, z + 1);
}
return;
}
int gao0()
{
gao0ans = 1;
dfs(n, n, 0);
return gao0ans;
}
int gao1()
{
map<ll ll> f[7501];
for (int i = 0; i <= n; i++)
{
f[i].clear();
}
f[0][1] = 1;
for (int k = 1; k <= n; k++) { for (int i = n; i > 0; i--)
{
for (int l = 1; l * k <= i; l++)
{
for (pair<ll ll> j: f[i - k * l])
{
// f[i - k * l][j] -> f[i][lcm(k, j)]
// ll tmp = f[i - k * l][j.first] * P(i, k * l)
ll tmp = j.second;
// cout << tmp << ' ' << i << ' ' << k * l << ' ' << P(i, k * l) << endl;
tmp = tmp * calc(i, k, l) % modd;
ll &t = f[i][lcm(k, j.first)];
t = (t + tmp) % modd;
}
}
}
}
ll ans = 1;
for (pair<ll int> j: f[n])
{
// cout << j.first << ' ' << j.second << endl;
ans = ans * pw(j.first, j.second, mod) % mod;
}
return ans % mod;
}
ll f[7520][13];
int gao2()
{
int g[7520] = {};
ll ans = 1;
for (int q = 0; q < pc; q++)
{
// cout << q[p] << endl;
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
for (int i = 1; i <= n; i++)
{
int j = i;
while (j % p[q] == 0)
{
g[i]++;
j /= p[q];
}
}
f[0][0] = 1;
for (int k = 1; k <= n; k++) { for (int i = n; i > 0; i--)
{
for (int l = 1; l * k <= i; l++)
{
for (int j = 0; j < 13; j++) { // f[i - k * l][j] -> f[i][max(g[k], j)]
// ll tmp = f[i - k * l][j] * P(i, k * l)
ll tmp = f[i - k * l][j];
// cout << tmp << ' ' << i << ' ' << k * l << ' ' << P(i, k * l) << endl;
tmp = tmp * calc(i, k, l) % modd;
ll &t = f[i][max(g[k], j)];
t = (t + tmp) % modd;
}
}
}
}
for (int j = 0; j < 13; j++)
{
ans = ans * pw(pw(p[q], j, mod), f[n][j], mod) % mod;
}
}
return ans;
}</ll></ll></ll>
namespace gao3
{
int f[7520];
inline void backward(int k, int s)
{
for (int i = n % s; i <= n; i += s)
{
for (int l = 1; l * k <= i; l++) { // f[i] = (f[i] + modd - FMD.reduce((ull)f[i - k * l] * calc(i, k, l))); f[i] = (f[i] + modd - FMD.reduce(FMD.reduce((ull)f[i - k * l] * c[i][k*l]) * cc[k][l])); if (f[i] >= modd)
{
f[i] -= modd;
}
}
}
}
int gao3()
{
ll ans = 1;
for (int q = 0; q < pc; q++)
{
// if (q < 4)
// printf("LINE %d %d %.3fseconds\n", __LINE__, p[q], clock()/1e6);
vector<int> g[14];
// cout << q[p] << endl;
memset(f, 0, sizeof f);
f[0] = 1;
int mc = 0;
for (int i = 1; i <= n; i++) { f[i] = FMD.reduce((ull)f[i - 1] * i) % modd; int j = i; int c = 0; while (j % p[q] == 0) { c++; j /= p[q]; } g[c].push_back(i); mc = max(mc, c); } ll lastf = f[n]; for (int j = mc; j >= 1; j--)
{
for (int k: g[j])
{
backward(k, p[q]);
}
ans = ans * pw(pw(p[q], j, mod), (lastf - f[n] + modd), mod) % mod;
lastf = f[n];
}
}
return ans;
}
// 枚举质数 \sum (n/质数 * n/质数 log n)
}</int>
namespace gao4
{
int f[7520];
int g[7520];
vector<int> divisors[14];
inline void backward(int pk, int p, int ppk)
{
for (int i = n % p; i <= n; i += p)
{
for (int j = 1; j * ppk <= i; j++) { f[i] = (f[i] + modd - FMD.reduce(FMD.reduce((ull)f[i - j * ppk] * c[i][j * ppk]) * g[j])); if (f[i] >= modd)
{
f[i] -= modd;
}
}
}
}
int gao4()
{
ll ans = 1;
for (int q = 0; q < pc; q++)
{
memset(f, 0, sizeof f);
f[0] = 1;
int mc = 0;
for (int i = 0; i < 14; i++)
{
divisors[i].clear();
}
for (int i = 1; i <= n; i++) { f[i] = FMD.reduce((ull)f[i - 1] * i) % modd; int j = i; int c = 0; while (j % p[q] == 0) { c++; j /= p[q]; } divisors[c].push_back(i); mc = max(mc, c); } ll lastf = f[n]; for (int j = mc; j >= 1; j--)
{
int ppk = 1;
for (int k = 0; k < j; k++)
{
ppk *= p[q];
}
memset(g, 0, sizeof g);
g[0] = 1;
for (int i = 0; i * ppk <= n; i++)
{
for (int j = 1; j <= i; j++) { if (j % p[q] == 0) { continue; } g[i] = (g[i] + FMD.reduce(FMD.reduce(c[i * ppk - 1][j * ppk - 1] * fac[j * ppk - 1]) * g[i - j])); if (g[i] >= modd)
{
g[i] -= modd;
}
}
}
backward(j, p[q], ppk);
// cout << p[q] << ' ' << j << ' ' << (lastf - f[n] + modd) % modd << endl; ans = ans * pw(pw(p[q], j, mod), (lastf - f[n] + modd), mod) % mod; lastf = f[n]; } } return ans; } // 枚举质数 \sum (n/质数 * n/质数 log n) } int main() { freopen("exercise.in", "r", stdin); freopen("exercise.out", "w", stdout); cin >> n >> mod;
modd = mod - 1;
FM = FastMod(mod);
FMD = FastMod(mod - 1);
fac[0] = 1;
invfac[0] = 1;
for (int i = 0; i <= n; i++)
{
c[i][0] = 1;
for (int j = 1; j <= n; j++) { c[i][j] = (c[i-1][j-1] + c[i-1][j]); if (c[i][j] >= modd)
{
c[i][j] -= modd;
}
}
}
// for (int i = 1; i <= n; i++)
// {
// cc[i].resize(n / i + 1);
// cc[i][0] = 1;
// for (int j = 1; i * j <= n; j++)
// {
// cc[i][j] = cc[i][j - 1];
// for (int k = i * j - i + 1; k < i * j; k++)
// {
// cc[i][j] = FMD.reduce((ull)cc[i][j] * k);
// }
// }
// }</int>
for (int i = 1; i <= n; i++)
{
if (isPrime(i))
{
p[pc++] = i;
}
fac[i] = fac[i - 1] * i % modd;
// inv[i] = pw(i, mod - 2, mod);
// invfac[i] = pw(fac[i], mod - 2, mod);
}
// printf("%d\n", gao0());
// printf("%d\n", gao1());
// printf("%d\n", gao2());
// printf("LINE %d %.3fseconds\n", __LINE__, clock()/1e6);
// printf("%d\n", gao3::gao3());
// printf("LINE %d %.3fseconds\n", __LINE__, clock()/1e6);
printf("%d\n", gao4::gao4());
// printf("LINE %d %.3fseconds\n", __LINE__, clock()/1e6);
// printf("%lld\n", timecount);
// printf("LINE %d %.3fseconds\n", __LINE__, clock()/1e6);
return 0;
}
/*
把n分成若干部分
n = 12
n = 2 + 2 + 2 + 3 + 3
方案数
12! / 2 / 2 / 2 / 3 / 3 / 3! / 2!
6! / 2 / 2 / 2 / 3! * P(12, 6) / 3 / 3 / 2!
// n x y
// n! / (n - x*y)! / pow(x, y) / y!
sqrt(7500)一下的质数，暴力去记录次幂，以上的，依次处理
2 0..12
3 0..8
5 0..5
7 0..4
11 0..3
13 0..3
17 0..3
19 0..3
23 0..2
29 0..2
31 0..2
37 0..2
41 0..2
43 0..2
47 0..2
53 0..2
59 0..2
61 0..2
67 0..2
71 0..2
73 0..2
79 0..2
83 0..2
f[i][j]
当前加到k数字
所有数字之和是i
所有数字的lcm是j
方案数是...
*/
P3
“`cpp
#include <bits>
using namespace std;
int n, x, y;
vector<int> a[100020];
vector<int> d[100020];
vector<pair int> > e[100020];
vector<pair int> > b[100020];
int c[100020];
int f[100020];
int fac[100020];
int inv[100020];
int invfac[100020];
int z[100020];
const int mod = 1000000007;
int F(int x)
{
return f[x] != x ? f[x] = F(f[x]) : x;
}
void dfs(int x, int y, int r, int h)
{
if (d[r].size() <= h) { d[r].push_back(0); } d[r][h]++; if (x != r && a[x].size() >= 3)
{
if (x < r)
{
e[h].push_back(make_pair(x, r));
}
return;
}
for (int i: a[x])
{
if (i != y)
{
dfs(i, x, r, h + 1);
}
}
}
int main()
{
freopen("circus.in", "r", stdin);
freopen("circus.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
fac[0] = 1;
invfac[0] = 1;
inv[1] = 1;
z[n] = 1;
for (int i = 2; i <= n; i++)
{
inv[i] = (long long)inv[mod % i] * (mod – mod / i) % mod;
}
for (int i = 1; i <= n; i++)
{
fac[i] = (long long)fac[i – 1] * i % mod;
invfac[i] = (long long)invfac[i – 1] * inv[i] % mod;
}
z[n] = fac[n];</pair></pair></int></int></bits>
set<int> roots;</int>
for (int i = 1; i <= n; i++) { f[i] = i; if (a[i].size() >= 3)
{
roots.insert(i);
dfs(i, 0, i, 0);
for (int j = 0; j < d[i].size(); j++) { b[j].push_back(make_pair(i, d[i][j])); } } } for (int i = n – 1; i > 0; i–)
{
z[i] = (long long)z[i + 1] * inv[i + 1] % mod;
for (int j: roots)
{
z[i] = (long long)z[i] * fac[c[j] – (n – 1 – i)] % mod;
}
for (pair<int int> j: b[n – 1 – i])
{
c[F(j.first)] += j.second;
}
for (pair<int int> j: e[n – 2 – i])
{
// assert(F(j.first) != F(j.second));
int x = F(j.first);
int y = F(j.second);
c[y] = c[x] + c[y] – (n – 1 – i);
f[x] = y;
roots.erase(x);
}
for (int j: roots)
{
z[i] = (long long)z[i] * invfac[c[j] – (n – i)] % mod;
}
}
for (int i = 1; i <= n; i++)
{
printf("%d\n", z[i]);
}
return 0;
}
“`