{"id":248,"date":"2020-04-27T03:17:52","date_gmt":"2020-04-26T19:17:52","guid":{"rendered":"https:\/\/wwwwodddd.com\/?p=248"},"modified":"2020-05-05T19:47:00","modified_gmt":"2020-05-05T11:47:00","slug":"usaco-2020-open","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/usaco-2020-open\/","title":{"rendered":"USACO 2020 OPEN"},"content":{"rendered":"

<\/p>\n

Overall<\/h1>\n

Bronze<\/h1>\n

B1<\/h2>\n
#include <bits>\n\nusing namespace std;\n\nchar s[100020];\n\nint n;\n\nint main()\n\n{\n\nfreopen(\"socdist1.in\", \"r\", stdin);\n\nfreopen(\"socdist1.out\", \"w\", stdout);\n\nscanf(\"%d\", &n);\n\nscanf(\"%s\", s);\n\nint prev = -1;\n\nvector<int> d;\n\nint first = -1;\n\nint last = -1;\n\nint cowcnt = 0;\n\nfor (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)\n\n{\n\nans = max(ans, min(d[0], d.back() \/ 3));\n\n}\n\nif (cowcnt >= 3)\n\n{\n\nans = max(ans, min(d[0], d[d.size() - 2] \/ 2));\n\n}\n\n}\n\nprintf(\"%d\\n\", ans);\n\nreturn 0;\n\n}\n\n```<\/int><\/bits>\n\n## B2\n```cpp\n#include <bits>\n\nusing namespace std;\n\npair<int int> a[100020];\n\nint main()\n\n{\n\nfreopen(\"socdist2.in\", \"r\", stdin);\n\nfreopen(\"socdist2.out\", \"w\", stdout);\n\nint n;\n\ncin >> n;\n\nfor (int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second;\n\n}\n\nsort(a, a + n);\n\nint d = 1e9;\n\nfor (int i = 1; i < n; i++)\n\n{\n\nif (a[i].second + a[i - 1].second == 1)\n\n{\n\nd = min(d, a[i].first - a[i - 1].first);\n\n}\n\n}\n\nint ans = 0;\n\nfor (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)\n\n{\n\nans++;\n\n}\n\n}\n\n}\n\nprintf(\"%d\\n\", ans);\n\nreturn 0;\n\n}\n\n```<\/int><\/bits>\n\n## B3\n```cpp\n#include <bits>\n\nusing namespace std;\n\nint n, m;\n\nchar s[120];\n\nchar c[120];\n\nint d[120];\n\npair<int pair int> > a[260];\n\nbool check(int root, int times)\n\n{\n\nfor (int i = 0; i < n; i++)\n\n{\n\nc[i] = '0';\n\nd[i] = times;\n\n}\n\nc[root] = '1';\n\nfor (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)\n\n{\n\nd[a[i].second.second]--;\n\nc[a[i].second.first] = '1';\n\n}\n\n}\n\nelse if (c[a[i].second.first] == '1' && c[a[i].second.second] == '0')\n\n{\n\nif (d[a[i].second.first] > 0)\n\n{\n\nd[a[i].second.first]--;\n\nc[a[i].second.second] = '1';\n\n}\n\n}\n\nelse if (c[a[i].second.first] == '1' && c[a[i].second.second] == '1')\n\n{\n\nif (d[a[i].second.first] > 0)\n\n{\n\nd[a[i].second.first]--;\n\n}\n\nif (d[a[i].second.second] > 0)\n\n{\n\nd[a[i].second.second]--;\n\n}\n\n}\n\n}\n\nreturn strcmp(s, c) == 0;\n\n}\n\nint main()\n\n{\n\nfreopen(\"tracing.in\", \"r\", stdin);\n\nfreopen(\"tracing.out\", \"w\", stdout);\n\nscanf(\"%d%d\", &n, &m);\n\nscanf(\"%s\", s);\n\nfor (int i = 0; i < m; i++)\n\n{\n\nscanf(\"%d%d%d\", &a[i].first, &a[i].second.first, &a[i].second.second);\n\na[i].second.first--;\n\na[i].second.second--;\n\n}\n\nsort(a, a + m);\n\nint rootcnt = 0;\n\nint mink = m + 1;\n\nint maxk = 0;\n\nfor (int i = 0; i < n; i++)\n\n{\n\nbool cani = false;\n\nfor (int k = 0; k <= m + 1; k++)\n\n{\n\nif (check(i, k))\n\n{\n\nmink = min(mink, k);\n\nmaxk = max(maxk, k);\n\ncani = true;\n\n}\n\n}\n\nif (cani)\n\n{\n\nrootcnt++;\n\n}\n\n}\n\nprintf(\"%d %d \", rootcnt, mink);\n\nif (maxk != m + 1)\n\n{\n\nprintf(\"%d\\n\", maxk);\n\n}\n\nelse\n\n{\n\nprintf(\"Infinity\\n\");\n\n}\n\nreturn 0;\n\n}\n\n```<\/int><\/bits>\n\n## S1\n```cpp\n#include <bits>\n\nusing namespace std;\n\nint n, m;\n\npair<long long> a[100020];\n\nbool check(long long d)\n\n{\n\nint cnt = 0;\n\nlong long s = a[0].first;\n\nint i = 0;\n\nwhile (true)\n\n{\n\nif (a[i].first <= s && s <= a[i].second) { cnt++; if (cnt >= m)\n\n{\n\nreturn true;\n\n}\n\ns += d;\n\n}\n\nwhile (i < n && s > a[i].second)\n\n{\n\ni++;\n\n}\n\nif (i == n)\n\n{\n\nbreak;\n\n}\n\nif (s < a[i].first) { s = a[i].first; } } return cnt >= m;\n\n}\n\nint main()\n\n{\n\nfreopen(\"socdist.in\", \"r\", stdin);\n\nfreopen(\"socdist.out\", \"w\", stdout);\n\nscanf(\"%d%d\", &m, &n);\n\nfor (int i = 0; i < n; i++)\n\n{\n\nscanf(\"%lld%lld\", &a[i].first, &a[i].second);\n\n}\n\nsort(a, a + n);\n\nlong long L = 0;\n\nlong long R = 1e18 + 1;\n\nwhile (L < R - 1)\n\n{\n\nlong long M = (L + R) \/ 2;\n\nif (check(M))\n\n{\n\nL = M;\n\n}\n\nelse\n\n{\n\nR = M;\n\n}\n\n}\n\nprintf(\"%lld\\n\", L);\n\nreturn 0;\n\n}\n\n```<\/long><\/bits>\n\n## S2\n```cpp\n#include <bits>\n\nusing namespace std;\n\nint n, m;\n\nint a[100020][2];\n\nint z[100020];\n\nint v[100020];\n\nint main()\n\n{\n\nfreopen(\"cereal.in\", \"r\", stdin);\n\nfreopen(\"cereal.out\", \"w\", stdout);\n\ncin >> n >> m;\n\nfor (int i = 1; i <= n; i++) { cin >> a[i][0] >> a[i][1];\n\n}\n\nfor (int i = n; i > 0; i--)\n\n{\n\nint j = i;\n\nz[i] = z[i + 1];\n\nwhile (true)\n\n{\n\nif (v[a[j][0]] == 0)\n\n{\n\nv[a[j][0]] = j;\n\nz[i]++;\n\nbreak;\n\n}\n\nelse if (v[a[j][0]] > j)\n\n{\n\nint nj = v[a[j][0]];\n\nv[a[j][0]] = j;\n\nj = nj;\n\n}\n\nelse if (v[a[j][1]] == 0)\n\n{\n\nv[a[j][1]] = j;\n\nz[i]++;\n\nbreak;\n\n}\n\nelse if (v[a[j][1]] > j)\n\n{\n\nint nj = v[a[j][1]];\n\nv[a[j][1]] = j;\n\nj = nj;\n\n}\n\nelse\n\n{\n\nbreak;\n\n}\n\n}\n\n}\n\nfor (int i = 1; i <= n; i++)\n\n{\n\nprintf(\"%d\\n\", z[i]);\n\n}\n\nreturn 0;\n\n}\n\n```<\/bits>\n\n## S3\n```cpp\n#include <bits>\n\nusing namespace std;\n\nint n;\n\nint x[100020];\n\nint y[100020];\n\nint r1[100020];\n\nint r2[100020];\n\nint q[100020];\n\nint p[100020];\n\nbool cmp1(int a, int b)\n\n{\n\nreturn 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]);\n\n}\n\nint main()\n\n{\n\nfreopen(\"moop.in\", \"r\", stdin);\n\nfreopen(\"moop.out\", \"w\", stdout);\n\ncin >> n;\n\nfor (int i = 0; i < n; i++) { cin >> x[i] >> y[i];\n\nr1[i] = i;\n\nr2[i] = i;\n\n}\n\nsort(r1, r1 + n, cmp1);\n\nsort(r2, r2 + n, cmp2);\n\n\/\/ for (int i = 0; i < n; i++)\n\n\/\/ {\n\n\/\/  printf(\"%d \", r1[i]);\n\n\/\/ }\n\n\/\/ printf(\"\\n\");\n\n\/\/ for (int i = 0; i < n; i++)\n\n\/\/ {\n\n\/\/  printf(\"%d \", r2[i]);\n\n\/\/ }\n\n\/\/ printf(\"\\n\");\n\nfor (int i = 0; i < n; i++)\n\n{\n\nq[r1[i]] = i;\n\n}\n\nfor (int i = 0; i < n; i++)\n\n{\n\np[i] = q[r2[i]];\n\n}\n\n\/\/ for (int i = 0; i < n; i++)\n\n\/\/ {\n\n\/\/  printf(\"%d \", p[i]);\n\n\/\/ }\n\n\/\/ printf(\"\\n\");\n\nint mx = 0;\n\nint ans = 0;\n\nfor (int i = 0; i < n; i++)\n\n{\n\nmx = max(mx, p[i]);\n\nif (mx == i)\n\n{\n\nans++;\n\n}\n\n}\n\nprintf(\"%d\\n\", ans);\n\nreturn 0;\n\n}\n\n```<\/bits>\n\n## G1\n```cpp\n#include <bits>\n\nusing namespace std;\n\nint n;\n\nint c[100020];\n\nvoid change(int x, int y)\n\n{\n\nfor (x++; x <= n + 1; x += x & -x) { c[x] += y; } } int query(int x) { int re = 0; for (x++; x > 0; x -= x & -x)\n\n{\n\nre += c[x];\n\n}\n\nreturn re;\n\n}\n\nlong long z[100020];\n\nint main()\n\n{\n\nfreopen(\"haircut.in\", \"r\", stdin);\n\nfreopen(\"haircut.out\", \"w\", stdout);\n\ncin >> n;\n\nfor (int i = 0; i < n; i++) { int x; cin >> x;\n\nint u = i - query(x);\n\nz[x] -= u;\n\nz[n] += u;\n\nchange(x, 1);\n\n}\n\nfor (int i = n - 1; i >= 0; i--)\n\n{\n\nz[i] += z[i + 1];\n\n}\n\nfor (int i = 0; i < n; i++)\n\n{\n\nprintf(\"%lld\\n\", z[i]);\n\n}\n\nreturn 0;\n\n}\n\n```<\/bits>\n\n## G2\n```cpp\n#include <bits>\n\nusing namespace std;\n\nint n, m;\n\nint f[200020];\n\nint c[200020], cc;\n\nvector<int> a[200020];\n\nset<int> q;\n\nint F(int x)\n\n{\n\nreturn f[x] != x ? f[x] = F(f[x]) : x;\n\n}\n\nvoid U(int x, int y)\n\n{\n\nx = F(x);\n\ny = F(y);\n\nif (x == y)\n\n{\n\nreturn;\n\n}\n\nif (x > y)\n\n{\n\nswap(x, y);\n\n}\n\nf[y] = x;\n\nif (a[x].size() < a[y].size())\n\n{\n\na[x].swap(a[y]);\n\n}\n\nfor (int i: a[y])\n\n{\n\na[x].push_back(F(i));\n\n}\n\na[y].clear();\n\n}\n\nint main()\n\n{\n\nfreopen(\"fcolor.in\", \"r\", stdin);\n\nfreopen(\"fcolor.out\", \"w\", stdout);\n\nscanf(\"%d%d\", &n, &m);\n\nfor (int i = 0; i < m; i++)\n\n{\n\nint x, y;\n\nscanf(\"%d%d\", &y, &x);\n\na[y].push_back(x);\n\n}\n\nfor (int i = 1; i <= n; i++) { f[i] = i; if (a[i].size() > 1)\n\n{\n\nq.insert(i);\n\n}\n\n}\n\nwhile (q.size())\n\n{\n\nint u = *q.begin();\n\nu = F(u);\n\nq.erase(q.begin());\n\nfor (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)\n\n{\n\nint base = a[u][0];\n\nfor (int i = 1; i < a[u].size(); i++) { U(base, a[u][i]); } base = F(base); if (a[base].size() > 1)\n\n{\n\nq.insert(base);\n\n}\n\n}\n\n}\n\nfor (int i = 1; i <= n; i++)\n\n{\n\nif (c[F(i)] == 0)\n\n{\n\nc[F(i)] = ++cc;\n\n}\n\nprintf(\"%d\\n\", c[F(i)]);\n\n}\n\nreturn 0;\n\n}\n\n```<\/int><\/int><\/bits>\n\n## G3\n```cpp\n#include <bits>\n\nusing namespace std;\n\ntypedef long long ll;\n\nint n, mod;\n\nint p[10020], pc;\n\nint isPrime(int x)\n\n{\n\nif (x < 2)\n\n{\n\nreturn false;\n\n}\n\nfor (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;\n\nfor (int i = 1; i <= n; i++)\n\n{\n\nif (isPrime(i))\n\n{\n\np[pc++] = i;\n\n}\n\n}\n\nfor (int i = 0; i <= n; i++)\n\n{\n\nf[i] = 1;\n\n}\n\nfor (int i = 0; i < pc; i++) { for (int j = n; j > 0; j--)\n\n{\n\nfor (int k = p[i]; k <= j; k *= p[i])\n\n{\n\nf[j] = (f[j] + f[j - k] * k) % mod;\n\n}\n\n}\n\n}\n\nprintf(\"%lld\\n\", f[n]);\n\nreturn 0;\n\n}\n\n```<\/bits>\n\n## P1\n```cpp\n#include <bits>\n\nusing namespace std;\n\nconst int mod = 1000000007;\n\nconst int inv2 = 500000004;\n\nint n;\n\nint f[2020][2020]; \/\/ (i, j - 1) -> (i, j)\n\nint g[2020][2020]; \/\/ (i - 1, j) -> (i, j)\n\nchar s[2020][2020];<\/bits>\n\nint main()\n{\nfreopen(\"sprinklers2.in\", \"r\", stdin);\nfreopen(\"sprinklers2.out\", \"w\", stdout);\nint n;\nscanf(\"%d\", &n);\nfor (int i = 0; i < n; i++)\n{\nscanf(\"%s\", s[i]);\n}\nfor (int i = 1; i <= n; i++)\n{\nf[0][i] = 1;\ng[i][0] = 1;\n}\nfor (int i = 1; i <= n; i++)\n{\nfor (int j = 1; j <= n; j++)\n{\nf[i][j] = f[i][j-1];\nif (s[i-1][j-1] != 'W')\n{\nf[i][j] = (f[i][j] + (long long)g[i][j-1] * inv2) % mod;\n}\ng[i][j] = g[i-1][j];\nif (s[i-1][j-1] != 'W')\n{\ng[i][j] = (g[i][j] + (long long)f[i-1][j] * inv2) % mod;\n}\n}\n}\nint ans = (f[n][n] + g[n][n]) % mod;\nfor (int i = 0; i < n; i++)\n{\nfor (int j = 0; j < n; j++)\n{\nif (s[i][j] == '.')\n{\nans = ans * 2 % mod;\n}\n}\n}\nprintf(\"%d\\n\", ans);\nreturn 0;\n}\n<\/code><\/pre>\n
P2<\/h2>\n
#include <bits>\n\nusing namespace std;\n\ntypedef long long ll;\n\nint n, mod, modd;\n\nll fac[7520];\n\nll inv[7520];\n\nll invfac[7520];\n\nint p[1000], pc;\n\ntypedef unsigned long long ull;\n\ntypedef __uint128_t L;\n\nstruct FastMod {\n\null b, m;\n\nFastMod(ull b) : b(b), m(ull((L(1) << 64) \/ b)) {} ull reduce(ull a) { ull q = (ull)((L(m) * a) >> 64);\n\null r = a - q * b; \/\/ can be proven that 0 <= r < 2*b return r >= b ? r - b : r;\n\n}\n\n}FM(2), FMD(2);\n\nint isPrime(int x)\n\n{\n\nif (x < 2)\n\n{\n\nreturn false;\n\n}\n\nfor (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)\n\n{\n\nif (y & 1)\n\n{\n\nre = (re * x) % mod;\n\n}\n\nx = x * x % mod;\n\n}\n\nreturn re;\n\n}\n\nll gcd(ll x, ll y)\n\n{\n\nreturn y ? gcd(y, x % y) : x;\n\n}\n\nll lcm(ll x, ll y)\n\n{\n\nreturn x \/ gcd(x, y) * y;\n\n}\n\nll P(int n, int m)\n\n{\n\nassert(0 <= m && m <= n);\n\nreturn fac[n] * invfac[n - m] % mod;\n\n}\n\nint a[20];\n\nint b[20];\n\nlong long gao0ans = 1;<\/bits>\n\n\/\/ n x y\n\/\/ n! \/ (n - x*y)! \/ pow(x, y) \/ y!\n\/\/ C(n, x*y) * (x*y)! \/ pow(x, y) \/ y!\n\/\/ G(n, x, y) =\nint d1[7520];\nint d2[7520];\nunsigned c[7520][7520];\nvector<unsigned> cc[7520];\n\n\/\/ c[i][j] = c[i-1][j] + c[i-1][j-1]\n\nmap<pair int>, int> C[7520];\n\nll timecount = 0;\n\ninline ll calc(int n, int x, int y)\n\n{\n\ntimecount++;\n\nreturn FMD.reduce((ull)c[n][x * y] * cc[x][y]);\n\npair<int int> u = make_pair(x, y);\n\nif (C[n].find(u) != C[n].end())\n\n{\n\nreturn C[n][u];\n\n}\n\n\/\/ ll ret = c[n][x * y];\n\n\/\/ for (int i = 1; i <= x * y; i++)\n\n\/\/ {\n\n\/\/  ret = ret * i;\n\n\/\/  assert(ret < 1e60);\n\n\/\/ }\n\n\/\/ for (int i = 1; i <= y; i++)\n\n\/\/ {\n\n\/\/  ret = ret \/ x;\n\n\/\/  ret = ret \/ i;\n\n\/\/ }<\/int><\/pair><\/unsigned>\n\nfor (int i = 1; i <= y; i++)\n{\nd1[i] = x;\nd2[i] = i;\n}\nll re = c[n][x * y];\nfor (int i = 1; i <= x * y; i++)\n{\nint k = i;\nfor (int j = 1; j <= y; j++)\n{\nll g;\ng = gcd(k, d1[j]);\nk \/= g;\nd1[j] \/= g;\ng = gcd(k, d2[j]);\nk \/= g;\nd2[j] \/= g;\nif (k == 1)\n{\nbreak;\n}\n}\nre = re * k % modd;\n}\n\/\/ ret %= modd;\n\/\/ if (re != ret)\n\/\/ {\n\/\/  cout << n << ' ' << x << ' ' << y << ' ' << ret << ' ' << re << endl;\n\/\/ }\n\/\/ assert(re == ret);\nC[n][u] = re;\n\/\/ cout << n << ' ' << x << ' ' << y << ' ' << re << endl;\nassert((long long)c[n][x * y] * cc[x][y] % modd == re);\nreturn re;\n}\n\nvoid dfs(int x, int y, int z)\n{\nif (x == 0)\n{\nint l = 1;\nll sum = 1;\nint cnt = 0;\nfor (int i = 0; i < z; i++)\n{\nl = lcm(l, a[i]);\ncnt += a[i] * b[i];\nsum = sum * calc(cnt, a[i], b[i]) % modd;\n}\ngao0ans = gao0ans * pw(l, sum, mod) % mod;\n\/\/ for (int i = 0; i < z; i++)\n\/\/ {\n\/\/  printf(\"%d %d\\n\", a[i], b[i]);\n\/\/ }\n\/\/ printf(\"%lld %d\\n\", sum, cnt);\n\/\/ printf(\"------\\n\");\nreturn;\n}\nif (y == 0)\n{\nreturn;\n}\ndfs(x, y - 1, z);\na[z] = y;\nfor (b[z] = 1; b[z] * y <= x; b[z]++)\n{\ndfs(x - b[z] * y, y - 1, z + 1);\n}\nreturn;\n}\nint gao0()\n{\ngao0ans = 1;\ndfs(n, n, 0);\nreturn gao0ans;\n}\n\nint gao1()\n{\nmap<ll ll> f[7501];\n\nfor (int i = 0; i <= n; i++)\n\n{\n\nf[i].clear();\n\n}\n\nf[0][1] = 1;\n\nfor (int k = 1; k <= n; k++) { for (int i = n; i > 0; i--)\n\n{\n\nfor (int l = 1; l * k <= i; l++)\n\n{\n\nfor (pair<ll ll> j: f[i - k * l])\n\n{\n\n\/\/ f[i - k * l][j] -> f[i][lcm(k, j)]\n\n\/\/ ll tmp = f[i - k * l][j.first] * P(i, k * l)\n\nll tmp = j.second;\n\n\/\/ cout << tmp << ' ' << i << ' ' << k * l << ' ' << P(i, k * l) << endl;\n\ntmp = tmp * calc(i, k, l) % modd;\n\nll &t = f[i][lcm(k, j.first)];\n\nt = (t + tmp) % modd;\n\n}\n\n}\n\n}\n\n}\n\nll ans = 1;\n\nfor (pair<ll int> j: f[n])\n\n{\n\n\/\/ cout << j.first << ' ' << j.second << endl;\n\nans = ans * pw(j.first, j.second, mod) % mod;\n\n}\n\nreturn ans % mod;\n\n}\n\nll f[7520][13];\n\nint gao2()\n\n{\n\nint g[7520] = {};\n\nll ans = 1;\n\nfor (int q = 0; q < pc; q++)\n\n{\n\n\/\/ cout << q[p] << endl;\n\nmemset(f, 0, sizeof f);\n\nmemset(g, 0, sizeof g);\n\nfor (int i = 1; i <= n; i++)\n\n{\n\nint j = i;\n\nwhile (j % p[q] == 0)\n\n{\n\ng[i]++;\n\nj \/= p[q];\n\n}\n\n}\n\nf[0][0] = 1;\n\nfor (int k = 1; k <= n; k++) { for (int i = n; i > 0; i--)\n\n{\n\nfor (int l = 1; l * k <= i; l++)\n\n{\n\nfor (int j = 0; j < 13; j++) { \/\/ f[i - k * l][j] -> f[i][max(g[k], j)]\n\n\/\/ ll tmp = f[i - k * l][j] * P(i, k * l)\n\nll tmp = f[i - k * l][j];\n\n\/\/ cout << tmp << ' ' << i << ' ' << k * l << ' ' << P(i, k * l) << endl;\n\ntmp = tmp * calc(i, k, l) % modd;\n\nll &t = f[i][max(g[k], j)];\n\nt = (t + tmp) % modd;\n\n}\n\n}\n\n}\n\n}\n\nfor (int j = 0; j < 13; j++)\n\n{\n\nans = ans * pw(pw(p[q], j, mod), f[n][j], mod) % mod;\n\n}\n\n}\n\nreturn ans;\n\n}<\/ll><\/ll><\/ll>\n\nnamespace gao3\n{\nint f[7520];\ninline void backward(int k, int s)\n{\nfor (int i = n % s; i <= n; i += s)\n{\nfor (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)\n{\nf[i] -= modd;\n}\n}\n}\n}\nint gao3()\n{\nll ans = 1;\nfor (int q = 0; q < pc; q++)\n{\n\/\/ if (q < 4)\n\/\/ printf(\"LINE %d %d %.3fseconds\\n\", __LINE__, p[q], clock()\/1e6);\nvector<int> g[14];\n\n\/\/ cout << q[p] << endl;\n\nmemset(f, 0, sizeof f);\n\nf[0] = 1;\n\nint mc = 0;\n\nfor (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--)\n\n{\n\nfor (int k: g[j])\n\n{\n\nbackward(k, p[q]);\n\n}\n\nans = ans * pw(pw(p[q], j, mod), (lastf - f[n] + modd), mod) % mod;\n\nlastf = f[n];\n\n}\n\n}\n\nreturn ans;\n\n}\n\n\/\/ \u679a\u4e3e\u8d28\u6570 \\sum (n\/\u8d28\u6570 * n\/\u8d28\u6570 log n)\n\n}<\/int>\n\nnamespace gao4\n{\nint f[7520];\nint g[7520];\nvector<int> divisors[14];\n\ninline void backward(int pk, int p, int ppk)\n\n{\n\nfor (int i = n % p; i <= n; i += p)\n\n{\n\nfor (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)\n\n{\n\nf[i] -= modd;\n\n}\n\n}\n\n}\n\n}\n\nint gao4()\n\n{\n\nll ans = 1;\n\nfor (int q = 0; q < pc; q++)\n\n{\n\nmemset(f, 0, sizeof f);\n\nf[0] = 1;\n\nint mc = 0;\n\nfor (int i = 0; i < 14; i++)\n\n{\n\ndivisors[i].clear();\n\n}\n\nfor (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--)\n\n{\n\nint ppk = 1;\n\nfor (int k = 0; k < j; k++)\n\n{\n\nppk *= p[q];\n\n}\n\nmemset(g, 0, sizeof g);\n\ng[0] = 1;\n\nfor (int i = 0; i * ppk <= n; i++)\n\n{\n\nfor (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)\n\n{\n\ng[i] -= modd;\n\n}\n\n}\n\n}\n\nbackward(j, p[q], ppk);\n\n\/\/ 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; } \/\/ \u679a\u4e3e\u8d28\u6570 \\sum (n\/\u8d28\u6570 * n\/\u8d28\u6570 log n) } int main() { freopen(\"exercise.in\", \"r\", stdin); freopen(\"exercise.out\", \"w\", stdout); cin >> n >> mod;\n\nmodd = mod - 1;\n\nFM = FastMod(mod);\n\nFMD = FastMod(mod - 1);\n\nfac[0] = 1;\n\ninvfac[0] = 1;\n\nfor (int i = 0; i <= n; i++)\n\n{\n\nc[i][0] = 1;\n\nfor (int j = 1; j <= n; j++) { c[i][j] = (c[i-1][j-1] + c[i-1][j]); if (c[i][j] >= modd)\n\n{\n\nc[i][j] -= modd;\n\n}\n\n}\n\n}\n\n\/\/ for (int i = 1; i <= n; i++)\n\n\/\/ {\n\n\/\/  cc[i].resize(n \/ i + 1);\n\n\/\/  cc[i][0] = 1;\n\n\/\/  for (int j = 1; i * j <= n; j++)\n\n\/\/  {\n\n\/\/      cc[i][j] = cc[i][j - 1];\n\n\/\/      for (int k = i * j - i + 1; k < i * j; k++)\n\n\/\/      {\n\n\/\/          cc[i][j] = FMD.reduce((ull)cc[i][j] * k);\n\n\/\/      }\n\n\/\/  }\n\n\/\/ }<\/int>\n\nfor (int i = 1; i <= n; i++)\n{\nif (isPrime(i))\n{\np[pc++] = i;\n}\nfac[i] = fac[i - 1] * i % modd;\n\/\/ inv[i] = pw(i, mod - 2, mod);\n\/\/ invfac[i] = pw(fac[i], mod - 2, mod);\n}\n\/\/ printf(\"%d\\n\", gao0());\n\/\/ printf(\"%d\\n\", gao1());\n\/\/ printf(\"%d\\n\", gao2());\n\/\/ printf(\"LINE %d %.3fseconds\\n\", __LINE__, clock()\/1e6);\n\/\/ printf(\"%d\\n\", gao3::gao3());\n\/\/ printf(\"LINE %d %.3fseconds\\n\", __LINE__, clock()\/1e6);\nprintf(\"%d\\n\", gao4::gao4());\n\/\/ printf(\"LINE %d %.3fseconds\\n\", __LINE__, clock()\/1e6);\n\/\/ printf(\"%lld\\n\", timecount);\n\/\/ printf(\"LINE %d %.3fseconds\\n\", __LINE__, clock()\/1e6);\nreturn 0;\n}\n\/*\n\u628an\u5206\u6210\u82e5\u5e72\u90e8\u5206\n\nn = 12\n\nn = 2 + 2 + 2 + 3 + 3\n\n\u65b9\u6848\u6570\n12! \/ 2 \/ 2 \/ 2 \/ 3 \/ 3 \/ 3! \/ 2!\n\n6! \/ 2 \/ 2 \/ 2 \/ 3! * P(12, 6) \/ 3 \/ 3 \/ 2!\n\n\/\/ n x y\n\/\/ n! \/ (n - x*y)! \/ pow(x, y) \/ y!\n\nsqrt(7500)\u4e00\u4e0b\u7684\u8d28\u6570\uff0c\u66b4\u529b\u53bb\u8bb0\u5f55\u6b21\u5e42\uff0c\u4ee5\u4e0a\u7684\uff0c\u4f9d\u6b21\u5904\u7406\n\n2 0..12\n3 0..8\n5 0..5\n7 0..4\n11 0..3\n13 0..3\n17 0..3\n19 0..3\n23 0..2\n29 0..2\n31 0..2\n37 0..2\n41 0..2\n43 0..2\n47 0..2\n53 0..2\n59 0..2\n61 0..2\n67 0..2\n71 0..2\n73 0..2\n79 0..2\n83 0..2\n\nf[i][j]\n\u5f53\u524d\u52a0\u5230k\u6570\u5b57\n\u6240\u6709\u6570\u5b57\u4e4b\u548c\u662fi\n\u6240\u6709\u6570\u5b57\u7684lcm\u662fj\n\u65b9\u6848\u6570\u662f...\n*\/\n<\/code><\/pre>\n
P3<\/h2>\n
“`cpp
\n#include <bits><\/p>\n
using namespace std;<\/p>\n
int n, x, y;<\/p>\n
vector<int> a[100020];<\/p>\n
vector<int> d[100020];<\/p>\n
vector<pair int> > e[100020];<\/p>\n
vector<pair int> > b[100020];<\/p>\n
int c[100020];<\/p>\n
int f[100020];<\/p>\n
int fac[100020];<\/p>\n
int inv[100020];<\/p>\n
int invfac[100020];<\/p>\n
int z[100020];<\/p>\n
const int mod = 1000000007;<\/p>\n
int F(int x)<\/p>\n
{<\/p>\n
return f[x] != x ? f[x] = F(f[x]) : x;<\/p>\n
}<\/p>\n
void dfs(int x, int y, int r, int h)<\/p>\n
{<\/p>\n
if (d[r].size() <= h) { d[r].push_back(0); } d[r][h]++; if (x != r && a[x].size() >= 3)<\/p>\n
{<\/p>\n
if (x < r)<\/p>\n
{<\/p>\n
e[h].push_back(make_pair(x, r));<\/p>\n
}<\/p>\n
return;<\/p>\n
}<\/p>\n
for (int i: a[x])<\/p>\n
{<\/p>\n
if (i != y)<\/p>\n
{<\/p>\n
dfs(i, x, r, h + 1);<\/p>\n
}<\/p>\n
}<\/p>\n
}<\/p>\n
int main()<\/p>\n
{<\/p>\n
freopen("circus.in", "r", stdin);<\/p>\n
freopen("circus.out", "w", stdout);<\/p>\n
scanf("%d", &n);<\/p>\n
for (int i = 1; i < n; i++)<\/p>\n
{<\/p>\n
scanf("%d%d", &x, &y);<\/p>\n
a[x].push_back(y);<\/p>\n
a[y].push_back(x);<\/p>\n
}<\/p>\n
fac[0] = 1;<\/p>\n
invfac[0] = 1;<\/p>\n
inv[1] = 1;<\/p>\n
z[n] = 1;<\/p>\n
for (int i = 2; i <= n; i++)<\/p>\n
{<\/p>\n
inv[i] = (long long)inv[mod % i] * (mod – mod \/ i) % mod;<\/p>\n
}<\/p>\n
for (int i = 1; i <= n; i++)<\/p>\n
{<\/p>\n
fac[i] = (long long)fac[i – 1] * i % mod;<\/p>\n
invfac[i] = (long long)invfac[i – 1] * inv[i] % mod;<\/p>\n
}<\/p>\n
z[n] = fac[n];<\/pair><\/pair><\/int><\/int><\/bits><\/p>\n
set<int> roots;<\/int><\/p>\n
for (int i = 1; i <= n; i++) { f[i] = i; if (a[i].size() >= 3)
\n{
\nroots.insert(i);
\ndfs(i, 0, i, 0);
\nfor (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–)
\n{
\nz[i] = (long long)z[i + 1] * inv[i + 1] % mod;
\nfor (int j: roots)
\n{
\nz[i] = (long long)z[i] * fac[c[j] – (n – 1 – i)] % mod;
\n}
\nfor (pair<int int> j: b[n – 1 – i])<\/p>\n
{<\/p>\n
c[F(j.first)] += j.second;<\/p>\n
}<\/p>\n
for (pair<int int> j: e[n – 2 – i])<\/p>\n
{<\/p>\n
\/\/ assert(F(j.first) != F(j.second));<\/p>\n
int x = F(j.first);<\/p>\n
int y = F(j.second);<\/p>\n
c[y] = c[x] + c[y] – (n – 1 – i);<\/p>\n
f[x] = y;<\/p>\n
roots.erase(x);<\/p>\n
}<\/p>\n
for (int j: roots)<\/p>\n
{<\/p>\n
z[i] = (long long)z[i] * invfac[c[j] – (n – i)] % mod;<\/p>\n
}<\/p>\n
}<\/p>\n
for (int i = 1; i <= n; i++)<\/p>\n
{<\/p>\n
printf("%d\\n", z[i]);<\/p>\n
}<\/p>\n
return 0;<\/p>\n
}<\/p>\n
“`<\/int><\/int><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-248","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/248","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/comments?post=248"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/248\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=248"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}