{"id":161,"date":"2019-03-25T00:00:15","date_gmt":"2019-03-24T16:00:15","guid":{"rendered":"http:\/\/wwwwodddd.com\/?p=161"},"modified":"2019-03-26T21:32:31","modified_gmt":"2019-03-26T13:32:31","slug":"2019-51nod-2","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/2019-51nod-2\/","title":{"rendered":"2019\u5e74\u5341\u4e8c\u7701NOI\u7701\u9009\u8054\u8003\u6a21\u6d4b\uff08\u7b2c\u4e8c\u573a\uff09"},"content":{"rendered":"

<\/p>\n

P1<\/h1>\n

51nod 1850 \u62bd\u5361\u5927\u8d5b<\/a>
\n\u57fa\u672c\u548c\u76f4\u64ad\u8bb2\u7684\u4e00\u6837\uff0c\u5b9e\u73b0$2$\u4e2a\u51fd\u6570\uff0c\u52a0\u5165\u548c\u5220\u9664\u3002<\/p>\n

#include <bits\/stdc++.h>\nusing namespace std;\nstruct Node {\n    int A, G, P, i;\n}a[220][220];\nconst int mod = 1000000007;\nint n;\nbool operator<(const Node &a, const Node &b) {\n    return a.A < b.A;\n}\nvector<Node> b;\nint m[220];\nlong long f[220];\nint p[220];\nint v[220];\nint z[220];\nint inv(int x) {\n    return x == 1 ? 1 : (long long)(mod - mod \/ x) * inv(mod % x) % mod;\n}\nvoid del(int x) {\n    int invx = inv((mod + 1 - x) % mod);\n    for (int i = 1; i <= n; i++) {\n        f[i] = (f[i] - f[i - 1] * x % mod + mod) * invx % mod;\n    }\n}\nvoid add(int x) {\n    for (int i = n; i > 0; i--) {\n        f[i] = (f[i] * (mod + 1 - x) + f[i - 1] * x) % mod;\n    }\n}\nint main() {\n    scanf(\"%d\", &n);\n    for (int i = 0; i < n; i++) {\n        scanf(\"%d\", &m[i]);\n        int Q = 0;\n        for (int j = 0; j < m[i]; j++) {\n            scanf(\"%d%d%d\", &a[i][j].A, &a[i][j].G, &a[i][j].P);\n            a[i][j].G = (long long)(100 - a[i][j].G) * inv(100) % mod;\n            Q += a[i][j].P;\n            a[i][j].i = i;\n        }\n        Q = inv(Q);\n        for (int j = 0; j < m[i]; j++) {\n            a[i][j].P = (long long)a[i][j].P * Q % mod;\n            b.push_back(a[i][j]);\n        }\n    }\n    for (int i = 0; i < n; i++) {\n        scanf(\"%d\", &v[i]);\n    }\n    sort(b.begin(), b.end());\n    f[1] = 1;\n    for (int i = 0; i < b.size(); i++) {\n        del(p[b[i].i]);\n        for (int j = 0; j < n; j++) {\n            z[b[i].i] = (z[b[i].i] + f[n - j] * v[j] % mod * b[i].G % mod * b[i].P) % mod;\n        }\n        p[b[i].i] = (p[b[i].i] + b[i].P) % mod;\n        add(p[b[i].i]);\n    }\n    for (int i = 0; i < n; i++) {\n        printf(\"%d\\n\", z[i]);\n    }\n    return 0;\n}\n<\/code><\/pre>\n
P2<\/h1>\n
51nod 1984 \u5f02\u6216\u7ea6\u6570\u548c<\/a>
\n\u57fa\u672c\u548c\u76f4\u64ad\u8bb2\u7684\u4e00\u6837\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nlong long S(long long n) {\n    long long re = 0;\n    for (long long i = n \/ 4 * 4; i < n; i++) {\n        re ^= i;\n    }\n    return re;\n}\nint main() {\n    long long n, ans = 0;\n    cin >> n;\n    for (long long i = 1, j; i <= n; i = j + 1) {\n        j = n \/ (n \/ i);\n        if ((n \/ i) & 1) {\n            ans ^= S(j + 1) ^ S(i);\n        }\n    }\n    cout << ans << endl;\n}\n<\/code><\/pre>\n
P3<\/h1>\n
51nod 2014 \u5c0f\u670b\u53cb\u7684\u7b11\u8bdd<\/a>
\n\u57fa\u672c\u548c\u76f4\u64ad\u8bb2\u7684\u4e0d\u4e00\u6837\u3002
\n\u53bb\u5077\u5e08\u4e86\u4e00\u4e2a\u53ef\u6301\u4e45\u5316\u7ebf\u6bb5\u6811\u590d\u5236\u5b50\u6811\u7684\u4ee3\u7801\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m, tt;\nint rt[100020];\nint s[5000020];\nint lc[5000020];\nint rc[5000020];\nint build(int l, int r) {\n    int now = ++tt;\n    s[now] = r - l + 1;\n    if (l == r) {\n        return now;\n    }\n    int mid = (l + r) \/ 2;\n    lc[now] = build(l, mid);\n    rc[now] = build(mid+1, r);\n    return now;\n}\nint query(int x, int l, int r, int L, int R) {\n    if (L <= l && r <= R) {\n        return s[x];\n    }\n    if (r < L || R < l) {\n        return 0;\n    }\n    int mid = (l + r) \/ 2;\n    return query(lc[x], l, mid, L, R) + query(rc[x], mid + 1, r, L, R);\n}\nint change(int x, int y, int l, int r, int L, int R) {\n    if (L <= l && r <= R) {\n        return y;\n    }\n    if (r < L || R < l) {\n        return x;\n    }\n    int now = ++tt;\n    int mid = (l + r) \/ 2;\n    lc[now] = change(lc[x], lc[y], l, mid, L, R);\n    rc[now] = change(rc[x], rc[y], mid + 1, r, L, R);\n    s[now] = s[lc[now]] + s[rc[now]];\n    return now;\n}\nint main() {\n    scanf(\"%d%d\", &n, &m);\n    rt[0] = build(1, n);\n    for (int i = 1; i <= 100000; i++) {\n        rt[i] = rt[0];\n    }\n    rt[0] = 0;\n    for (int i = 0; i < m; i++) {\n        int o, l, r, k;\n        scanf(\"%d\", &o);\n        if (o == 1) {\n            scanf(\"%d%d%d\", &l, &k, &r);\n            l -= r;\n            r = l + 2 * r;\n            l = max(l, 1);\n            r = min(r, n);\n            rt[0] = change(rt[0], rt[k], 1, n, l, r);\n            rt[k] = change(rt[k], 0, 1, n, l, r);\n        } else {\n            scanf(\"%d%d\", &l, &r);\n            printf(\"%d\\n\", query(rt[0], 1, n, l, r));\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-161","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/161","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=161"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/161\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=161"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=161"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=161"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}