{"id":210,"date":"2019-12-18T00:00:59","date_gmt":"2019-12-17T16:00:59","guid":{"rendered":"https:\/\/wwwwodddd.com\/?p=210"},"modified":"2020-02-01T20:30:45","modified_gmt":"2020-02-01T12:30:45","slug":"usaco-2019-dec","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/usaco-2019-dec\/","title":{"rendered":"USACO 2019 DEC"},"content":{"rendered":"

<\/p>\n

Bronze<\/h1>\n

B1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint b[30][30];\nint a[30];\nint main()\n{\n    freopen(\"gymnastics.in\", \"r\", stdin);\n    freopen(\"gymnastics.out\", \"w\", stdout);\n    int m, n;\n    scanf(\"%d%d\", &m, &n);\n    for (int i = 0; i < m; i++)\n    {\n        for (int j = 0; j < n; j++)\n        {\n            scanf(\"%d\", &a[j]);\n        }\n        for (int j = 0; j < n; j++)\n        {\n            for (int k = 0; k < j; k++)\n            {\n                b[a[k]][a[j]]++;\n            }\n        }\n    }\n    int ans = 0;\n    for (int j = 1; j <= n; j++)\n    {\n        for (int k = 1; k <= n; k++)\n        {\n            if (b[j][k] == m)\n            {\n                ans++;\n            }\n        }\n    }\n    printf(\"%d\\n\", ans);\n    return 0;\n}\n<\/code><\/pre>\n
B2<\/h2>\n
import sys\nsys.stdin = open('whereami.in', 'r')\nsys.stdout = open('whereami.out', 'w')\nn = input()\ns = raw_input()\nfor l in range(1, n + 1):\n    if len(set([s[i:i+l] for i in range(n - l + 1)])) == n - l + 1:\n        print l\n        break\n<\/code><\/pre>\n
B3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nstring s[8] = {\"Bessie\", \"Buttercup\", \"Belinda\", \"Beatrice\", \"Bella\", \"Blue\", \"Betsy\", \"Sue\"};\nstring a[7], b[7], c, d, e, f;\nint n;\nbool good(string a, string b)\n{\n    for (int i = 0; i < 7; i++)\n    {\n        if (s[i] == a && s[i + 1] == b)\n        {\n            return true;\n        }\n        if (s[i] == b && s[i + 1] == a)\n        {\n            return true;\n        }\n    }\n    return false;\n}\nbool ok()\n{\n    for (int i = 0; i < n; i++)\n    {\n        if (!good(a[i], b[i]))\n        {\n            return false;\n        }\n    }\n    return true;\n}\nint main()\n{\n    freopen(\"lineup.in\", \"r\", stdin);\n    freopen(\"lineup.out\", \"w\", stdout);\n    cin >> n;\n    for (int i = 0; i < n; i++)\n    {\n        cin >> a[i] >> c >> d >> e >> f >> b[i];\n    }\n    sort(s, s + 8);\n    do\n    {\n        if (ok())\n        {\n            for (int i = 0; i < 8; i++)\n            {\n                cout << s[i] << endl;\n            }\n            break;\n        }\n    }\n    while(next_permutation(s, s + 8));\n    return 0;\n}\n<\/code><\/pre>\n
Silver<\/h1>\n
S1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nlong long calc(long long n)\n{\n    return n - n \/ 3 - n \/ 5 + n \/ 15;\n}\nint main()\n{\n    freopen(\"moobuzz.in\", \"r\", stdin);\n    freopen(\"moobuzz.out\", \"w\", stdout);\n    long long n;\n    cin >> n;\n    long long L = 0;\n    long long R = 2 * n;\n    while (L < R - 1)\n    {\n        int M = (L + R) \/ 2;\n        if (calc(M) < n)\n        {\n            L = M;\n        }\n        else\n        {\n            R = M;\n        }\n    }\n    cout << R << endl;\n    return 0;\n}\n<\/code><\/pre>\n
S2<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\npair<int, int> a[100020];\npair<int, int> b[100020];\npair<int, int> w[100020];\nint n, l;\nlong long calc()\n{\n    long long re = 0;\n    long long cnt = 0;\n    for (int i = 0; i < n; i++)\n    {\n        if (b[i].second == -1)\n        {\n            cnt++;\n        }\n    }\n    for (int i = 0; i < n; i++)\n    {\n        if (b[i].second == -1)\n        {\n            cnt--;\n        }\n        else\n        {\n            re += cnt;\n        }\n    }\n    return re;\n}\nint main()\n{\n    freopen(\"meetings.in\", \"r\", stdin);\n    freopen(\"meetings.out\", \"w\", stdout);\n    int sum = 0, cur = 0;\n    scanf(\"%d%d\", &n, &l);\n    int L = 0;\n    int R = n;\n    for (int i = 0; i < n; i++)\n    {\n        int d;\n        scanf(\"%d%d%d\", &w[i].second, &w[i].first, &d);\n        b[i].first = w[i].first;\n        b[i].second = d;\n        sum += w[i].second;\n        if (d == -1)\n        {\n            a[i] = make_pair(w[i].first, 0); \/\/ left;\n        }\n        else\n        {\n            a[i] = make_pair(l - w[i].first, 1); \/\/ right;\n        }\n    }\n    sort(w, w + n);\n    sort(a, a + n);\n    int tim = -1;\n    for (int i = 0; i < n; i++)\n    {\n        if (a[i].second == 0)\n        {\n            cur += w[L++].second;\n        }\n        else\n        {\n            cur += w[--R].second;\n        }\n        if (cur * 2 >= sum)\n        {\n            tim = a[i].first;\n            break;\n        }\n    }\n    sort(b, b + n);\n    long long ans = calc();\n    for (int i = 0; i < n; i++)\n    {\n        b[i].first += b[i].second * tim;\n    }\n    sort(b, b + n);\n    ans -= calc();\n    printf(\"%lld\\n\", ans);\n    return 0;\n}\n<\/code><\/pre>\n
S3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nchar s[100020];\nvector<int> a[100020];\nint f[100020][20];\nint c[100020];\nint d[100020];\nvoid dfs(int x, int y)\n{\n    f[x][0] = y;\n    d[x] = d[y] + 1;\n    c[x] = c[y] + (s[x] == 'G');\n    for (int i = 1; i < 20; i++)\n    {\n        f[x][i] = f[f[x][i - 1]][i - 1];\n    }\n    for (int i : a[x])\n    {\n        if (i != y)\n        {\n            dfs(i, x);\n        }\n    }\n}\nint lca(int x, int y)\n{\n    if (d[x] < d[y])\n    {\n        swap(x, y);\n    }\n    int dd = d[x] - d[y];\n    for (int i = 0; i < 20; i++)\n    {\n        if (dd >> i & 1)\n        {\n            x = f[x][i];\n        }\n    }\n    if (x == y)\n    {\n        return x;\n    }\n    for (int i = 20 - 1; i >= 0; i--)\n    {\n        if (f[x][i] != f[y][i])\n        {\n            x = f[x][i];\n            y = f[y][i];\n        }\n    }\n    return f[x][0];\n}\nint main()\n{\n    freopen(\"milkvisits.in\", \"r\", stdin);\n    freopen(\"milkvisits.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    scanf(\"%s\", s + 1);\n    for (int i = 1; i < n; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &x, &y);\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0);\n    for (int i = 0; i < m; i++)\n    {\n        int x, y;\n        char o[2];\n        scanf(\"%d%d%s\", &x, &y, o);\n        int l = lca(x, y);\n        int dxy = d[x] + d[y] - 2 * d[l] + 1;\n        int cxy = c[x] + c[y] - 2 * c[l] + (s[l] == 'G');\n        if (o[0] == 'G')\n        {\n            printf(\"%d\", cxy > 0);\n        }\n        else\n        {\n            printf(\"%d\", cxy < dxy);\n        }\n    }\n    printf(\"\\n\");\n    return 0;\n}\n<\/code><\/pre>\n
Gold<\/h1>\n
G1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\npair<pair<int, int>, pair<int, int> > b[1020];\nvector<pair<int, int> > a[1020];\npriority_queue<pair<int, int> > q;\nint d[100020];\nint dijk()\n{\n    memset(d, 0x3f, sizeof d);\n    d[1] = 0;\n    q.push(make_pair(-d[1], 1));\n    while (q.size() > 0)\n    {\n        pair<int, int> u = q.top();\n        q.pop();\n        if (-u.first > d[u.second])\n        {\n            continue;\n        }\n        for (int i = 0; i < a[u.second].size(); i++)\n        {\n            pair<int, int> e = a[u.second][i];\n            if (d[e.first] > d[u.second] + e.second)\n            {\n                d[e.first] = d[u.second] + e.second;\n                q.push(make_pair(-d[e.first], e.first));\n            }\n        }\n    }\n    return d[n];\n}\nint main()\n{\n    freopen(\"pump.in\", \"r\", stdin);\n    freopen(\"pump.out\", \"w\", stdout);\n    cin >> n >> m;\n    for (int i = 0; i < m; i++)\n    {\n        cin >> b[i].second.first >> b[i].second.second >> b[i].first.second >> b[i].first.first;\n    }\n    sort(b, b + m);\n    long long ans = 0;\n    for (int i = m - 1; i >= 0; i--)\n    {\n        a[b[i].second.first].push_back(make_pair(b[i].second.second, b[i].first.second));\n        a[b[i].second.second].push_back(make_pair(b[i].second.first, b[i].first.second));\n        ans = max(ans, 1000000LL * b[i].first.first \/ dijk());\n    }\n    cout << ans << endl;\n    return 0;\n}\n<\/code><\/pre>\n
G2<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nint cl[100020];\nvector<int> cc[100020];\nvector<int> a[100020];\nint f[100020][20];\nint c[100020];\nint d[100020];\nint L[100020];\nint R[100020];\nint s[100020], ss;\nchar z[100020];\nvector<pair<pair<int, int>, int> > q[100020];\nvoid change(int x, int y)\n{\n    for (; x <= n; x += x & -x)\n    {\n        c[x] += y;\n    }\n}\nint query(int x)\n{\n    int re = 0;\n    for (; x > 0; x -= x & -x)\n    {\n        re += c[x];\n    }\n    return re;\n}\nvoid dfs(int x, int y)\n{\n    L[x] = ss;\n    s[ss++] = x;\n    f[x][0] = y;\n    d[x] = d[y] + 1;\n    for (int i = 1; i < 20; i++)\n    {\n        f[x][i] = f[f[x][i - 1]][i - 1];\n    }\n    for (int i : a[x])\n    {\n        if (i != y)\n        {\n            dfs(i, x);\n        }\n    }\n    R[x] = ss;\n}\nint lca(int x, int y)\n{\n    if (d[x] < d[y])\n    {\n        swap(x, y);\n    }\n    int dd = d[x] - d[y];\n    for (int i = 0; i < 20; i++)\n    {\n        if (dd >> i & 1)\n        {\n            x = f[x][i];\n        }\n    }\n    if (x == y)\n    {\n        return x;\n    }\n    for (int i = 20 - 1; i >= 0; i--)\n    {\n        if (f[x][i] != f[y][i])\n        {\n            x = f[x][i];\n            y = f[y][i];\n        }\n    }\n    return f[x][0];\n}\nint main()\n{\n    freopen(\"milkvisits.in\", \"r\", stdin);\n    freopen(\"milkvisits.out\", \"w\", stdout);\n    ss = 1;\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 1; i <= n; i++)\n    {\n        scanf(\"%d\", &cl[i]);\n        cc[cl[i]].push_back(i);\n    }\n    for (int i = 1; i < n; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &x, &y);\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0);\n    for (int i = 0; i < m; i++)\n    {\n        int x, y, o;\n        scanf(\"%d%d%d\", &x, &y, &o);\n        q[o].push_back(make_pair(make_pair(x, y), i));\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        for (int j = 0; j < cc[i].size(); j++)\n        {\n            change(L[cc[i][j]], 1);\n            change(R[cc[i][j]], -1);\n        }\n        for (int j = 0; j < q[i].size(); j++)\n        {\n            int x = q[i][j].first.first;\n            int y = q[i][j].first.second;\n            int l = lca(x, y);\n            int cnt = query(L[x]) + query(L[y]) - 2 * query(L[l]) + (cl[l] == i);\n            z[q[i][j].second] = (cnt > 0) + '0';\n        }\n        for (int j = 0; j < cc[i].size(); j++)\n        {\n            change(L[cc[i][j]], -1);\n            change(R[cc[i][j]], 1);\n        }\n    }\n    printf(\"%s\\n\", z);\n    return 0;\n}\n<\/code><\/pre>\n
G3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m, l;\nchar c[100020];\nint s[100020][30];\nint f[100020][30];\nint a[30][30];\nint main()\n{\n    freopen(\"cowmbat.in\", \"r\", stdin);\n    freopen(\"cowmbat.out\", \"w\", stdout);\n    scanf(\"%d%d%d\", &n, &m, &l);\n    scanf(\"%s\", c + 1);\n    for (int i = 0; i < m; i++)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            scanf(\"%d\", &a[i][j]);\n        }\n    }\n    for (int k = 0; k < m; k++)\n    {\n        for (int i = 0; i < m; i++)\n        {\n            for (int j = 0; j < m; j++)\n            {\n                if (a[i][j] > a[i][k] + a[k][j])\n                {\n                    a[i][j] = a[i][k] + a[k][j];\n                }\n            }\n        }\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            s[i][j] = s[i - 1][j] + a[c[i] - 'a'][j];\n        }\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            f[i][j] = f[i - 1][j] + a[c[i] - 'a'][j];\n        }\n        if (i >= l)\n        {\n            int tmp = 1e9;\n            for (int j = 0; j < m; j++)\n            {\n                tmp = min(tmp, f[i - l][j] + s[i][j] - s[i - l][j]);\n            }\n            for (int j = 0; j < m; j++)\n            {\n                f[i][j] = min(f[i][j], tmp);\n            }\n            if (i == n)\n            {   \n                printf(\"%d\\n\", tmp);\n            }\n        }\n    }\n    return 0;\n}\n<\/code><\/pre>\n
Platinum<\/h1>\n
P1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nint f[320][320][9][9];\nint a[320][320];\nint g[320][320];\nint fastlg[320];\nint query(int x1, int y1, int x2, int y2)\n{\n    int dx = fastlg[x2 - x1 + 1], dy = fastlg[y2 - y1 + 1];\n    return max(max(f[x1][y1][dx][dy], f[x2 - (1 << dx) + 1][y1][dx][dy]), max(f[x1][y2 - (1 << dy) + 1][dx][dy], f[x2 - (1 << dx) + 1][y2 - (1 << dy) + 1][dx][dy]));\n}\nint main()\n{\n    freopen(\"pieaters.in\", \"r\", stdin);\n    freopen(\"pieaters.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 2; i < 310; i++)\n    {\n        fastlg[i] = fastlg[i \/ 2] + 1;\n    }\n    for (int i = 0; i < m; i++)\n    {\n        int z, x, y;\n        scanf(\"%d%d%d\", &z, &x, &y);\n        x--;\n        y--;\n        a[x][y] = z;\n    }\n    for (int i = 0; i < n; i++)\n    {\n        for (int j = 0; j < n; j++)\n        {\n            f[i][j][0][0] = a[i][j];\n        }\n    }\n    for (int k = 0; 1 << k <= n; k++)\n        for (int l = 0; 1 << l <= n; l++)\n            if (k + l)\n                for (int i = 0; i + (1 << k) <= n; i++)\n                    for (int j = 0; j + (1 << l) <= n; j++)\n                    {\n                        if (k)\n                        {\n                            f[i][j][k][l] = max(f[i][j][k - 1][l], f[i + (1 << (k - 1))][j][k - 1][l]);\n                        }\n                        else\n                        {\n                            f[i][j][k][l] = max(f[i][j][k][l - 1], f[i][j + (1 << (l - 1))][k][l - 1]);\n                        }\n                    }\n    for (int l = 0; l < n; l++)\n    {\n        for (int i = 0; i + l < n; i++)\n        {\n            int j = i + l;\n            for (int k = i; k < j; k++)\n            {\n                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j]);\n            }\n            for (int k = i + 1; k < j; k++)\n            {\n                g[i][j] = max(g[i][j], g[i][k - 1] + g[k + 1][j] + query(i, k + 1, k - 1, j));\n            }\n            g[i][j] = max(g[i][j], g[i][j - 1] + query(i, j, j, j));\n            g[i][j] = max(g[i][j], g[i + 1][j] + query(i, i, i, j));\n        }\n    }\n    printf(\"%d\\n\", g[0][n - 1]);\n    return 0;\n}\n<\/code><\/pre>\n
P2<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nvector<int> a[100020];\nint L[100020];\nint R[100020];\nint s[100020], ss;\nint sz[100020];\nchar z[100020];\nset<pair<int, int> > op[100020];\n\nlong long tsz[400020];\nlong long sm[400020];\nint tmd[400020];\nvoid build(int x, int l, int r)\n{\n    if (l + 1 == r)\n    {\n        tsz[x] = 1;\n        return;\n    }\n    int m = (l + r) \/ 2;\n    build(2 * x, l, m);\n    build(2 * x + 1, m, r);\n    tsz[x] = tsz[2 * x] + tsz[2 * x + 1];\n}\nvoid push(int x)\n{\n    tmd[2 * x] += tmd[x];\n    sm[2 * x] += tsz[2 * x] * tmd[x];\n    tmd[2 * x + 1] += tmd[x];\n    sm[2 * x + 1] += tsz[2 * x + 1] * tmd[x];\n    tmd[x] = 0;\n}\nvoid change(int x, int l, int r, int L, int R, int v)\n{\n    \/\/ if (x == 1)\n    \/\/ printf(\"change %d %d %d %d %d %d\\n\", x, l, r, L, R, v);\n    if (r <= L || R <= l)\n    {\n        return;\n    }\n    if (L <= l && r <= R)\n    {\n        tmd[x] += v;\n        sm[x] += tsz[x] * v;\n        return;\n    }\n    push(x);\n    int m = (l + r) \/ 2;\n    change(2 * x, l, m, L, R, v);\n    change(2 * x + 1, m, r, L, R, v);\n    sm[x] = sm[2 * x] + sm[2 * x + 1];\n}\nlong long query(int x, int l, int r, int L,int R)\n{\n    \/\/ printf(\"query %d %d %d %d %d\\n\", x, l, r, L, R);\n    if (r <= L || R <= l)\n    {\n        return 0;\n    }\n    if (L <= l && r <= R)\n    {\n        return sm[x];\n    }\n    push(x);\n    int m = (l + r) \/ 2;\n    return query(2 * x, l, m, L, R) + query(2 * x + 1, m, r, L, R);\n}\n\nvoid dfs(int x, int y)\n{\n    L[x] = ss;\n    s[ss++] = x;\n    sz[x] = 1;\n    for (int i : a[x])\n    {\n        if (i != y)\n        {\n            dfs(i, x);\n            sz[x] += sz[i];\n        }\n    }\n    R[x] = ss;\n}\n\nint main()\n{\n    freopen(\"snowcow.in\", \"r\", stdin);\n    freopen(\"snowcow.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 1; i < n; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &x, &y);\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0);\n    build(1, 0, n);\n    for (int i = 0; i < m; i++)\n    {\n        int x, y, o;\n        scanf(\"%d\", &o);\n        if (o == 1)\n        {\n            scanf(\"%d%d\", &x, &y);\n            set<pair<int, int> >::iterator it = op[y].upper_bound(make_pair(L[x], R[x]));\n            if (it != op[y].begin())\n            {\n                if ((--it)->second >= R[x])\n                {\n                    continue;\n                }\n            }\n            while (true)\n            {\n                set<pair<int, int> >::iterator it = op[y].upper_bound(make_pair(L[x], R[x]));\n                if (it == op[y].end() || R[x] <= it->first)\n                {\n                    break;\n                }\n                change(1, 0, n, it->first, it->second, -1);\n                op[y].erase(it);\n            }\n            change(1, 0, n, L[x], R[x], 1);\n            op[y].insert(make_pair(L[x], R[x]));\n        }\n        else\n        {\n            scanf(\"%d\", &x);\n            printf(\"%lld\\n\", query(1, 0, n, L[x], R[x]));\n        }\n    }\n    return 0;\n}\n<\/code><\/pre>\n
P3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m, mod;\n\nint fs[320][45020];\nint gs[320][45020];\nint hs[320][45020];\nint ans2[320];\nint ans3[320];\nint F(int x, int y)\n{\n    int re = fs[x][y + 1] - fs[x][y];\n    if (re < 0)\n    {\n        re += mod;\n    }\n    return re;\n}\nint G(int x, int y)\n{\n    int re = gs[x][y + 1] - gs[x][y];\n    if (re < 0)\n    {\n        re += mod;\n    }\n    return re;\n}\nint H(int x, int y)\n{\n    int re = hs[x][y + 1] - hs[x][y];\n    if (re < 0)\n    {\n        re += mod;\n    }\n    return re;\n}\nvoid caonima()\n{\n    \/\/ f[len][inversion] = sum of such number;\n    \/\/ g[len][inversion] = the number of such permutation;\n    memset(fs, 0, sizeof fs);\n    memset(gs, 0, sizeof gs);\n    memset(hs, 0, sizeof hs);\n    for (int j = 0; j <= n * (n - 1) \/ 2; j++)\n    {\n        gs[1][j + 1] = (gs[1][j] + (j == 0)) % mod;\n    }\n\n    for (int i = 2; i <= n; i++)\n    {\n        int fucklimit = i * (i - 1) \/ 2;\n        for (int j = 0; j <= fucklimit; j++)\n        {\n            int kk = max(j - (i - 2), 0);\n            int nf = (fs[i - 1][j + 1] - fs[i - 1][kk] + mod) % mod;\n            int ng = (gs[i - 1][j + 1] - gs[i - 1][kk] + mod) % mod;\n            if (j - (i - 1) >= 0)\n            {\n                nf = ((long long)nf + F(i - 1, j - (i - 1)) + G(i - 1, j - (i - 1))) % mod;\n                ng = (ng + G(i - 1, j - (i - 1))) % mod;\n            }\n            fs[i][j + 1] = (fs[i][j] + nf) % mod;\n            gs[i][j + 1] = (gs[i][j] + ng) % mod;\n        }\n        for (int j = fucklimit + 1; j <= n * (n - 1) \/ 2; j++)\n        {\n            fs[i][j + 1] = (fs[i][j]) % mod;\n            gs[i][j + 1] = (gs[i][j]) % mod;\n        }\n    }\n    for (int j = 0; j <= n * (n - 1) + 1; j++)\n    {\n        hs[0][j + 1] = (hs[0][j] + (j == 0)) % mod;\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        for (int j = 0; j <= n * (n - 1) \/ 2; j++)\n        {\n            int kk = max(0, j - (n - i));\n            int nh = (hs[i - 1][j + 1] - hs[i - 1][kk] + mod) % mod;\n            hs[i][j + 1] = (hs[i][j] + nh) % mod;\n        }\n    }\n}\n\nvoid gao3()\n{\n    caonima();\n    for (int i = 0; i < n; i++)\n    {\n        for (int j = 0; j <= m; j++)\n        {\n            \/\/ cerr << i << \" \" << j << \" \" << h[i][j] << \" \" << f[n - i][m - j] << endl;\n            ans3[i] = (ans3[i] + (long long)H(i, j) * F(n - i, m - j)) % mod;\n        }\n    }\n    m = n * (n - 1) \/ 2 - m;\n    caonima();\n    reverse(ans3, ans3 + n);\n    for (int i = 0; i < n; i++)\n    {\n        for (int j = 0; j <= m; j++)\n        {\n            \/\/ cerr << i << \" \" << j << \" \" << h[i][j] << \" \" << f[n - i][m - j] << endl;\n            ans3[i] = (ans3[i] + (long long)H(i, j) * F(n - i, m - j)) % mod;\n        }\n    }\n    reverse(ans3, ans3 + n);\n    m = n * (n - 1) \/ 2 - m;\n    for (int i = 0; i < n; i++)\n    {\n        ans3[i] = (ans3[i] + H(n, m)) % mod;\n    }\n}\n\nint main()\n{\n    freopen(\"treedepth.in\", \"r\", stdin);\n    freopen(\"treedepth.out\", \"w\", stdout);\n    scanf(\"%d%d%d\", &n, &m, &mod);\n    \/\/ gao1();\n    \/\/ for (int i = 0; i < n; i++)\n    \/\/ {\n    \/\/  printf(\"%d%c\", ans1[i], i == n - 1 ? '\\n' : ' ');\n    \/\/ }\n    \/\/ gao2();\n    \/\/ for (int i = 0; i < n; i++)\n    \/\/ {\n    \/\/  printf(\"%d%c\", ans2[i], i == n - 1 ? '\\n' : ' ');\n    \/\/ }\n    gao3();\n    for (int i = 0; i < n; i++)\n    {\n        printf(\"%d%c\", ans3[i], i == n - 1 ? '\\n' : ' ');\n    }\n    return 0;\n}\n<\/code><\/pre>\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-210","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/210","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=210"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/210\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}