{"id":235,"date":"2020-02-27T17:02:55","date_gmt":"2020-02-27T09:02:55","guid":{"rendered":"https:\/\/wwwwodddd.com\/?p=235"},"modified":"2020-02-27T17:02:55","modified_gmt":"2020-02-27T09:02:55","slug":"usaco-2020-feb","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/usaco-2020-feb\/","title":{"rendered":"USACO 2020 FEB"},"content":{"rendered":"<p><!--more--><\/p>\n<h1>Overall<\/h1>\n<p>\u5728\u6bd4\u8d5b\u521a\u5f00\u59cb\u65f6\uff0c\u6240\u6709\u63d0\u4ea4\u90fd\u662f\u6587\u4ef6\u9519\u8bef\uff0c\u803d\u8bef\u4e86\u4e00\u4e9b\u65f6\u95f4\u3002<\/p>\n<h1>Bronze<\/h1>\n<h2>B1<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint x[120], y[120];\nint n, ans;\nint main()\n{\n    freopen(\"triangles.in\", \"r\", stdin);\n    freopen(\"triangles.out\", \"w\", stdout);\n    cin &gt;&gt; n;\n    for (int i = 0; i &lt; n; i++)\n    {\n        cin &gt;&gt; x[i] &gt;&gt; y[i];\n    }\n    for (int i = 0; i &lt; n; i++)\n    {\n        for (int j = 0; j &lt; n; j++)\n        {\n            if (x[i] == x[j])\n            {\n                for (int k = 0; k &lt; n; k++)\n                {\n                    if (y[i] == y[k])\n                    {\n                        ans = max(ans, abs((y[i] - y[j]) * (x[i] - x[k])));\n                    }\n                }\n            }\n        }\n    }\n    cout &lt;&lt; ans &lt;&lt; endl;\n    return 0;\n}\n<\/code><\/pre>\n<h2>B2<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n, z, l;\nstring a, b;\nint main()\n{\n    freopen(\"breedflip.in\", \"r\", stdin);\n    freopen(\"breedflip.out\", \"w\", stdout);\n    cin &gt;&gt; n &gt;&gt; a &gt;&gt; b;\n    for (int i = 0; i &lt; n; i++)\n    {\n        if (a[i] == b[i])\n        {\n            l = 0;\n        }\n        else\n        {\n            if (l == 0)\n            {\n                z++;\n            }\n            l = 1;\n        }\n    }\n    cout &lt;&lt; z &lt;&lt; endl;\n    return 0;\n}\n<\/code><\/pre>\n<h2>B3<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n, m, a1, b1, a2, b2;\nint a[120];\nbool ok()\n{\n    for (int i = 1; i &lt;= n; i++)\n    {\n        if (a[i] != i)\n        {\n            return false;\n        }\n    }\n    return true;\n}\nint main()\n{\n    freopen(\"swap.in\", \"r\", stdin);\n    FILE *fout = fopen(\"swap.out\", \"w\");\n    cin &gt;&gt; n &gt;&gt; m &gt;&gt; a1 &gt;&gt; b1 &gt;&gt; a2 &gt;&gt; b2;\n    for (int i = 1; i &lt;= n; i++)\n    {\n        a[i] = i;\n    }\n    for (int i = 1; i &lt;= m; i++)\n    {\n        reverse(a + a1, a + b1 + 1);\n        reverse(a + a2, a + b2 + 1);\n        if (ok())\n        {\n            m %= i;\n            m += i;\n        }\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        fprintf(fout, \"%d\\n\", a[i]);\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2>S1<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n, m, l;\nint a[100020];\nint b[100020];\nint r[100020];\nint c[100020];\nvoid mul(int a[], int b[])\n{\n    for (int i = 1; i &lt;= n; i++)\n    {\n        c[i] = a[b[i]];\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        a[i] = c[i];\n    }\n}\nint main()\n{\n    freopen(\"swap.in\", \"r\", stdin);\n    freopen(\"swap.out\", \"w\", stdout);\n    scanf(\"%d%d%d\", &amp;n, &amp;m, &amp;l);\n    for (int i = 1; i &lt;= n; i++)\n    {\n        a[i] = i;\n        b[i] = i;\n    }\n    for (int i = 0; i &lt; m; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &amp;x, &amp;y);\n        reverse(b + x, b + y + 1);\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        r[b[i]] = i;\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        b[i] = r[i];\n    }\n    for (; l &gt; 0; l &gt;&gt;= 1)\n    {\n        if (l &amp; 1)\n        {\n            mul(a, b);\n        }\n        mul(b, b);\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        r[a[i]] = i;\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        a[i] = r[i];\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        printf(\"%d\\n\", a[i]);\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2>S2<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nconst int mod = 1000000007;\nint sx[1000020];\nint sy[1000020];\nlong long ans = 0;\nmap&lt;int, vector&lt;pair&lt;int, int&gt; &gt; &gt; xx, yy;\nvoid gao(vector&lt;pair&lt;int, int&gt; &gt; &amp;a, int s[])\n{\n    sort(a.begin(), a.end());\n    long long s1 = 0, s2 = 0;\n    for (int i = 0; i &lt; a.size(); i++)\n    {\n        s2 += a[i].first;\n    }\n    for (int i = 0; i &lt; a.size(); i++)\n    {\n        s[a[i].second] = (i * a[i].first - s1) + (s2 - (a.size() - i) * a[i].first);\n        s1 += a[i].first;\n        s2 -= a[i].first;\n    }\n}\nint main()\n{\n    freopen(\"triangles.in\", \"r\", stdin);\n    freopen(\"triangles.out\", \"w\", stdout);\n    int n;\n    scanf(\"%d\", &amp;n);\n    for (int i = 0; i &lt; n; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &amp;x, &amp;y);\n        xx[x].push_back(make_pair(y, i));\n        yy[y].push_back(make_pair(x, i));\n    }\n    for (auto &amp;i: xx)\n    {\n        gao(i.second, sx);\n    }\n    for (auto &amp;i: yy)\n    {\n        gao(i.second, sy);\n    }\n    for (int i = 0; i &lt; n; i++)\n    {\n        ans = (ans + (long long)sx[i] * sy[i]) % mod;\n    }\n    printf(\"%d\\n\", (int)ans);\n    return 0;\n}\n<\/code><\/pre>\n<h2>S3<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n;\nint w[10020];\nint c[2], s[2];\nvector&lt;int&gt; a[10020];\nvoid dfs(int x, int y, int d)\n{\n    s[d] = (s[d] + w[x]) % 12;\n    c[d]++;\n    for (int i: a[x])\n    {\n        if (i != y)\n        {\n            dfs(i, x, d ^ 1);\n        }\n    }\n}\nint main()\n{\n    freopen(\"clocktree.in\", \"r\", stdin);\n    freopen(\"clocktree.out\", \"w\", stdout);\n    scanf(\"%d\", &amp;n);\n    for (int i = 1; i &lt;= n; i++)\n    {\n        scanf(\"%d\", &amp;w[i]);\n    }\n    for (int i = 1; i &lt; n; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &amp;x, &amp;y);\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0, 0);\n    if (s[0] == s[1])\n    {\n        printf(\"%d\\n\", n);\n    }\n    else if ((s[0] + 1) % 12 == s[1])\n    {\n        printf(\"%d\\n\", c[1]);\n    }\n    else if ((s[1] + 1) % 12 == s[0])\n    {\n        printf(\"%d\\n\", c[0]);\n    }\n    else\n    {\n        printf(\"0\\n\");\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2>G1<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n, m, c, x, y, z;\nvector&lt;pair&lt;int, int&gt; &gt; a[100020];\nint d[100020];\nint in[100020];\nqueue&lt;int&gt; q;\nint main()\n{\n    freopen(\"timeline.in\", \"r\", stdin);\n    freopen(\"timeline.out\", \"w\", stdout);\n    scanf(\"%d%d%d\", &amp;n, &amp;m, &amp;c);\n    for (int i = 1; i &lt;= n; i++)\n    {\n        scanf(\"%d\", &amp;d[i]);\n    }\n    for (int i = 0; i &lt; c; i++)\n    {\n        scanf(\"%d%d%d\", &amp;x, &amp;y, &amp;z);\n        a[x].push_back(make_pair(y, z));\n        in[y]++;\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        if (in[i] == 0)\n        {\n            q.push(i);\n        }\n    }\n    while (q.size() &gt; 0)\n    {\n        int u = q.front();\n        q.pop();\n        for (pair&lt;int, int&gt; i: a[u])\n        {\n            if (d[i.first] &lt; d[u] + i.second)\n            {\n                d[i.first] = d[u] + i.second;\n            }\n            if (!--in[i.first])\n            {\n                q.push(i.first);\n            }\n        }\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        printf(\"%d\\n\", d[i]);\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2>G2<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nconst int mod = 1000000007;\nint n, x, y, z, c;\nint a[200020];\nint b[200020];\nint main()\n{\n    freopen(\"help.in\", \"r\", stdin);\n    freopen(\"help.out\", \"w\", stdout);\n    scanf(\"%d\", &amp;n);\n    for (int i = b[0] = 1; i &lt;= n; i++)\n    {\n        b[i] = b[i - 1] * 2 % mod;\n    }\n    for (int i = 0; i &lt; n; i++)\n    {\n        scanf(\"%d%d\", &amp;x, &amp;y);\n        a[x] = +1;\n        a[y] = -1;\n    }\n    for (int i = 1; i &lt;= 2*n; i++)\n    {\n        c += a[i];\n        if (a[i] == 1)\n        {\n            z = (z + b[n - c]) % mod;\n        }\n    }\n    printf(\"%d\\n\", z);\n    return 0;\n}\n<\/code><\/pre>\n<h2>G3<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n;\nint s[100020];\nvector&lt;int&gt; a[100020];\nvector&lt;int&gt; b[100020];\nvoid dfs(int x, int y)\n{\n    s[x] = 1;\n    for (int i: a[x])\n    {\n        if (i != y)\n        {\n            dfs(i, x);\n            b[x].push_back(s[i]);\n            s[x] += s[i];\n        }\n    }\n}\nint ok(int l)\n{\n    if ((n - 1) % l != 0)\n    {\n        return 0;\n    }\n    for (int i = 1; i &lt;= n; i++)\n    {\n        vector&lt;int&gt; c;\n        for (int j: b[i])\n        {\n            j %= l;\n            if (j &gt; 0)\n            {\n                c.push_back(j);\n            }\n        }\n        if ((s[i] - 1) % l &gt; 0)\n        {\n            c.push_back(l - (s[i] - 1) % l);\n        }\n        sort(c.begin(), c.end());\n        if (c.size() % 2 &gt; 0)\n        {\n            return false;\n        }\n        for (int i = 0; i &lt; c.size(); i++)\n        {\n            if (c[i] + c[c.size() - 1 - i] != l)\n            {\n                return false;\n            }\n        }\n    }\n    return true;\n}\nint main()\n{\n    freopen(\"deleg.in\", \"r\", stdin);\n    freopen(\"deleg.out\", \"w\", stdout);\n    scanf(\"%d\", &amp;n);\n    for (int i = 1; i &lt; n; i++)\n    {\n        int x, y;\n        scanf(\"%d%d\", &amp;x, &amp;y);\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0);\n    for (int i = 1; i &lt; n; i++)\n    {\n        printf(\"%d\", ok(i));\n    }\n    printf(\"\\n\");\n    return 0;\n}\n<\/code><\/pre>\n<h2>P1<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n, x, y, z, M, flag;\nvector&lt;int&gt; a[100020];\n\nint dfs(int x, int y) {\n    multiset&lt;int&gt; b;\n    for (int i = 0; i &lt; a[x].size(); i++) {\n        if (a[x][i] != y) {\n            int l = dfs(a[x][i], x);\n            b.insert(l + 1);\n            if (!flag)\n            {\n                return 0;\n            }\n        }\n    }\n    int only = 0;\n    while (b.size() &gt; 1)\n    {\n        int u = *b.begin();\n        b.erase(b.begin());\n        if (u &lt; M)\n        {\n            multiset&lt;int&gt;::iterator it = b.lower_bound(M - u);\n            if (it == b.end())\n            {\n                if (only == 0)\n                {\n                    only = u;\n                    continue;\n                }\n                flag = false;\n                return 0;\n            }\n            if (b.size() == 1 &amp;&amp; *it &gt;= M)\n            {\n                return *b.begin();\n            }\n            b.erase(it);\n        }\n    }\n    if (b.size() == 0)\n    {\n        return only;\n    }\n    else\n    {\n        if (only &gt; 0)\n        {\n            flag = false;\n            return 0;\n        }\n        return *b.begin();\n    }\n}\nbool ok() {\n    flag = true;\n    int res = dfs(1, 0);\n    return flag &amp;&amp; (res &gt;= M || res == 0);\n}\nint main() {\n    freopen(\"deleg.in\", \"r\", stdin);\n    freopen(\"deleg.out\", \"w\", stdout);\n    scanf(\"%d\", &amp;n);\n    for (int i = 1; i &lt; n; i++) {\n        scanf(\"%d%d\", &amp;x, &amp;y);\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    int L = 1, R = n;\n    while (L &lt; R - 1) {\n        M = (L + R) \/ 2;\n        if (ok()) {\n            L = M;\n        } else {\n            R = M;\n        }\n    }\n    printf(\"%d\\n\", L);\n    return 0;\n}\n\n<\/code><\/pre>\n<h2>P2<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint n;\nchar s[320][320];\nint ul[320][320];\nint ur[320][320];\nlong long ans = 0;\nbool in(int x, int y)\n{\n    return 0 &lt; x &amp;&amp; x &lt;= n &amp;&amp; 0 &lt; y &amp;&amp; y &lt;= n;\n}\nint UL(int x, int y)\n{\n    int d = max(x - n, y - n);\n    if (d &gt; 0)\n    {\n        x -= d;\n        y -= d;\n    }\n    if (x &lt; 0 || y &lt; 0)\n    {\n        return 0;\n    }\n    return ul[x][y];\n}\nint UR(int x, int y)\n{\n    int d = max(x - n, 1 - y);\n    if (d &gt; 0)\n    {\n        x -= d;\n        y += d;\n    }\n    if (x &lt; 0 || y &gt; n)\n    {\n        return 0;\n    }\n    return ur[x][y];\n}\nvoid bf()\n{\n    int ans = 0;\n    for (int i = 0; i &lt; n * n; i++)\n    {\n        int x1 = i \/ n + 1;\n        int y1 = i % n + 1;\n        if (s[x1][y1] != '*')\n        {\n            continue;\n        }\n        for (int j = i + 1; j &lt; n * n; j++)\n        {\n            int x2 = j \/ n + 1;\n            int y2 = j % n + 1;\n            if (s[x2][y2] != '*')\n            {\n                continue;\n            }\n            for (int k = j + 1; k &lt; n * n; k++)\n            {\n                int x3 = k \/ n + 1;\n                int y3 = k % n + 1;\n                if (s[x3][y3] != '*')\n                {\n                    continue;\n                }\n                if (abs(x1 - x2) + abs(y1 - y2) != abs(x1 - x3) + abs(y1 - y3))\n                {\n                    continue;\n                }\n                if (abs(x1 - x2) + abs(y1 - y2) != abs(x2 - x3) + abs(y2 - y3))\n                {\n                    continue;\n                }\n                \/\/ cout &lt;&lt; i &lt;&lt; ' ' &lt;&lt; j &lt;&lt; ' ' &lt;&lt; k &lt;&lt; endl;\n                ans++;\n            }\n        }\n    }\n    cout &lt;&lt; ans &lt;&lt; endl;\n}\nint main()\n{\n    freopen(\"triangles.in\", \"r\", stdin);\n    freopen(\"triangles.out\", \"w\", stdout);\n    \/\/ srand(time(0));\n    scanf(\"%d\", &amp;n);\n    \/\/ n = 10;\n    for (int i = 1; i &lt;= n; i++)\n    {\n        scanf(\"%s\", s[i] + 1);\n        \/\/ for (int j = 1; j &lt;= n; j++)\n        \/\/ {\n        \/\/  s[i][j] = rand() &amp; 1 ? '*' : '.';\n        \/\/ }\n    }\n    \/\/ bf();\n    for (int i = 1; i &lt;= n; i++)\n    {\n        for (int j = 1; j &lt;= n; j++)\n        {\n            ul[i][j] = ul[i - 1][j - 1] + (s[i][j] == '*');\n            ur[i][j] = ur[i - 1][j + 1] + (s[i][j] == '*');\n        }\n    }\n    for (int x1 = 1; x1 &lt;= n; x1++)\n    {\n        for (int y1 = 1; y1 &lt;= n; y1++)\n        {\n            if (s[x1][y1] != '*')\n            {\n                continue;\n            }\n            for (int k = 1; k &lt;= n; k++)\n            {\n                int x2 = x1 + k;\n                int y2 = y1 - k;\n                if (in(x2, y2))\n                {\n                    if (s[x2][y2] == '*')\n                    {\n                        \/\/ cout &lt;&lt; x1 &lt;&lt; ' ' &lt;&lt; y1 &lt;&lt; ' ' &lt;&lt; x2 &lt;&lt; ' ' &lt;&lt; y2 &lt;&lt; ' ' &lt;&lt; ans &lt;&lt; endl;\n                        ans += UR(x2 + k, y2 + k) - UR(x1 + k - 1, y1 + k + 1);\n                        \/\/ cout &lt;&lt; x1 &lt;&lt; ' ' &lt;&lt; y1 &lt;&lt; ' ' &lt;&lt; x2 &lt;&lt; ' ' &lt;&lt; y2 &lt;&lt; ' ' &lt;&lt; ans &lt;&lt; endl;\n                        ans += UR(x2 - k, y2 - k) - UR(x1 - k - 1, y1 - k + 1);\n                        \/\/ cout &lt;&lt; UR(x2 - k, y2 - k) &lt;&lt; ' ' &lt;&lt; UR(x1 - k - 1, y1 - k + 1) &lt;&lt; endl;\n                        \/\/ cout &lt;&lt; x1 &lt;&lt; ' ' &lt;&lt; y1 &lt;&lt; ' ' &lt;&lt; x2 &lt;&lt; ' ' &lt;&lt; y2 &lt;&lt; ' ' &lt;&lt; ans &lt;&lt; endl;\n                    }\n                }\n                else\n                {\n                    break;\n                }\n            }\n            for (int k = 1; k &lt;= n; k++)\n            {\n                int x2 = x1 + k;\n                int y2 = y1 + k;\n                if (in(x2, y2))\n                {\n                    if (s[x2][y2] == '*')\n                    {\n                        ans += UL(x2 + k - 1, y2 - k - 1) - UL(x1 + k, y1 - k);\n                        ans += UL(x2 - k - 1, y2 + k - 1) - UL(x1 - k, y1 + k);\n                    }\n                }\n                else\n                {\n                    break;\n                }\n            }\n        }\n    }\n    cout &lt;&lt; ans &lt;&lt; endl;\n    return 0;\n}\n<\/code><\/pre>\n<h2>P3<\/h2>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n#include &lt;random&gt;\nusing namespace std;\nconst int mod = 1000000007;\nint n, m;\npair&lt;int, int&gt; a[100020];\nint pos[200020];\nint s[20][20];\nint fac[20];\nvoid bf()\n{\n    int ans = 0;\n    int v[100];\n    for (int i = 0; i &lt; 1 &lt;&lt; n; i++)\n    {\n        memset(v, 0, sizeof v);\n        for (int j = 0; j &lt; n; j++)\n        {\n            if (i &gt;&gt; j &amp; 1)\n            {\n                for (int k = a[j].first; k &lt; a[j].second; k++)\n                {\n                    v[k] = 1;\n                }\n            }\n        }\n        int cnt = 0;\n        for (int j = 0; j &lt; 2 * n; j++)\n        {\n            if (v[j] == 0 &amp;&amp; v[j + 1] == 1)\n            {\n                cnt++;\n            }\n        }\n        long long tmp = 1;\n        for (int j = 0; j &lt; m; j++)\n        {\n            tmp = tmp * cnt % mod;\n        }\n        ans = (ans + tmp) % mod;\n    }\n    printf(\"%d\\n\", ans);\n    return;\n}\nlong long f[100020][12];\nvoid work()\n{\n    \/\/f[i][j]=sum{f[k][j-1]*2^sum{[r[o]&lt;l[i]]}(k&lt;o&lt;i)}(r[k]&lt;l[i])\n    memset(f, 0, sizeof f);\n    f[0][0] = 1;\n    for (int j = 1; j &lt;= m + 1; j++)\n    {\n        for (int i = 0; i &lt;= n + 1; i++)\n        {\n            long long b = 1;\n            for (int k = i - 1; k &gt;= 0; k--)\n            {\n                if (a[k].second &lt; a[i].first)\n                {\n                    f[i][j] = (f[i][j] + f[k][j - 1] * b) % mod;\n                    \/\/ cout &lt;&lt; i &lt;&lt; ' ' &lt;&lt; j &lt;&lt; ' ' &lt;&lt; k &lt;&lt; ' ' &lt;&lt; b &lt;&lt; endl;\n                    b = b * 2 % mod;\n                }\n            }\n            \/\/ printf(\"f1 %d %d %lld\\n\", i, j, f[i][j]);\n        }\n    }\n    long long ans = 0;\n    for (int j = 0; j &lt;= m + 1; j++)\n    {\n        \/\/ for (int i = 0; i &lt;= n + 1; i++)\n        \/\/ {\n        \/\/  printf(\"%lld \", f[i][j]);\n        \/\/ }\n        \/\/ printf(\"\\n\");\n        \/\/ printf(\"%d %lld\\n\", j, f[n + 1][j]);\n    }\n    for (int j = 1; j &lt;= m; j++)\n    {\n        ans = (ans + f[n + 1][j + 1] * fac[j] % mod * s[m][j] % mod);\n    }\n    printf(\"%lld\\n\", ans);\n    return;\n}\n\nlong long g[300020];\nlong long h[300020];\n\nvoid build(int x, int l, int r)\n{\n    h[x] = 1;\n    g[x] = 0;\n    if (l == r)\n    {\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    build(x * 2, l, mid);\n    build(x * 2 + 1, mid + 1, r);\n}\n\nvoid change(int x, int l, int r, int p, int v)\n{\n    if (l == r)\n    {\n        g[x] = v;\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    if (p &lt;= mid)\n    {\n        change(x * 2, l, mid, p, v);\n    }\n    else\n    {\n        change(x * 2 + 1, mid + 1, r, p, v);\n    }\n    g[x] = (g[x * 2] * h[x * 2] + g[x * 2 + 1] * h[x * 2 + 1]) % mod;\n}\n\nvoid modify(int x, int l, int r, int p)\n{\n    if (l &gt; p)\n    {\n        return;\n    }\n    if (r &lt;= p)\n    {\n        h[x] = h[x] * 2 % mod;\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    modify(x * 2, l, mid, p);\n    modify(x * 2 + 1, mid + 1, r, p);\n    g[x] = (g[x * 2] * h[x * 2] + g[x * 2 + 1] * h[x * 2 + 1]) % mod;\n}\n\nlong long query(int x, int l, int r, int p)\n{\n    if (l &gt; p)\n    {\n        return 0;\n    }\n    if (r &lt;= p)\n    {\n        return g[x] * h[x];\n    }\n    int mid = (l + r) \/ 2;\n    return (query(x * 2, l, mid, p) + query(x * 2 + 1, mid + 1, r, p)) * h[x] % mod;\n}\n\nvoid work2()\n{\n    \/\/f[i][j]=sum{f[k][j-1]*2^sum{[r[o]&lt;l[i]]}(k&lt;o&lt;i)}(r[k]&lt;l[i])\n    memset(f, 0, sizeof f);\n    f[0][0] = 1;\n    for (int j = 1; j &lt;= m + 1; j++)\n    {\n        build(1, 0, n + 1);\n        for (int i = 0; i &lt;= n + 1; i++)\n        {\n            for (int k = i == 0 ? 0 : (a[i-1].first + 1); k &lt; a[i].first; k++)\n            {\n                if (pos[k] &gt;= 0)\n                {\n                    change(1, 0, n + 1, pos[k], f[pos[k]][j - 1]);\n                    modify(1, 0, n + 1, pos[k] - 1);\n                }\n            }\n            f[i][j] = query(1, 0, n + 1, i - 1);\n            \/\/ printf(\"f2 %d %d %lld\\n\", i, j, f[i][j]);\n        }\n    }\n    long long ans = 0;\n    for (int j = 0; j &lt;= m + 1; j++)\n    {\n        \/\/ for (int i = 0; i &lt;= n + 1; i++)\n        \/\/ {\n        \/\/  printf(\"%lld \", f[i][j]);\n        \/\/ }\n        \/\/ printf(\"\\n\");\n        \/\/ printf(\"%d %lld\\n\", j, f[n + 1][j]);\n    }\n    for (int j = 1; j &lt;= m; j++)\n    {\n        ans = (ans + f[n + 1][j + 1] * fac[j] % mod * s[m][j] % mod);\n    }\n    printf(\"%lld\\n\", ans);\n    return;\n}\nint data[200020];\nint main()\n{\n    freopen(\"help.in\", \"r\", stdin);\n    freopen(\"help.out\", \"w\", stdout);\n    srand(time(0));\n    scanf(\"%d%d\", &amp;n, &amp;m);\n    s[0][0]=1;\n    for (int i = 1; i &lt;= m; i++)\n    {\n        for (int j = 1; j &lt;= m; j++)\n        {\n            s[i][j] = ((long long)s[i - 1][j] * j + s[i - 1][j - 1]) % mod;\n        }\n    }\n    fac[0] = 1;\n    for (int i = 1; i &lt;= m; i++)\n    {\n        fac[i] = (long long)fac[i - 1] * i % mod;\n    }\n    for (int i = 0; i &lt; 2 * n; i++)\n    {\n        data[i] = i;\n    }\n    random_device rd;\n    mt19937 randomizer(rd());\n    shuffle(data, data + 2 * n, randomizer);\n    for (int i = 0; i &lt; n; i++)\n    {\n        a[i].first = data[2 * i] + 1;\n        a[i].second = data[2 * i + 1] + 1;\n        if (a[i].first &gt; a[i].second)\n        {\n            swap(a[i].first, a[i].second);\n        }\n        scanf(\"%d%d\", &amp;a[i].first, &amp;a[i].second);\n    }\n    \/\/ bf();\n    a[n] = make_pair(-1, 0);\n    a[n + 1] = make_pair(2 * n + 1, 2 * n + 2);\n    sort(a, a + n + 2);\n    for (int i = 1; i &lt;= n; i++)\n    {\n        pos[a[i].first] = -i;\n        pos[a[i].second] = i;\n    }\n    work();\n    work2();\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-235","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/235","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=235"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/235\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}