{"id":3316,"date":"2024-07-09T01:19:23","date_gmt":"2024-07-08T17:19:23","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=3316"},"modified":"2024-07-09T01:55:26","modified_gmt":"2024-07-08T17:55:26","slug":"luogu-p10221-%e7%9c%81%e9%80%89%e8%81%94%e8%80%83-2024-%e9%87%8d%e5%a1%91%e6%97%b6%e5%85%89","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-p10221-%e7%9c%81%e9%80%89%e8%81%94%e8%80%83-2024-%e9%87%8d%e5%a1%91%e6%97%b6%e5%85%89\/","title":{"rendered":"Luogu P10221. [\u7701\u9009\u8054\u8003 2024] \u91cd\u5851\u65f6\u5149"},"content":{"rendered":"

\u9996\u5148\u4f1a\u505a\u8fd9\u4e2a\u9898\u3002 https:\/\/www.luogu.com.cn\/problem\/P6846<\/p>\n

\nconst int N = 18;\n\nstruct Edge {\n    int a, b;\n    void in() {\n        RD(a, b); --a; --b;\n        a = _1(a); b = _1(b);\n    }\n    bool in(int s) {\n        return (s&amp;a)&amp;&amp;(s&amp;b);\n    }\n} E[N*N\/2];\n\nInt f[1&lt;&lt;N]; bool bad[1&lt;&lt;N];\nint n, m;\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\n#endif\n    RD(n, m); REP(i, m) E[i].in();\n\n<pre><code>FOR(s, 1, _1(n)) {\n    REP(i, m) if (E[i].in(s)) {\n        bad[s] = 1;\n        break;\n    }\n}\n\nf[0] = 1; FOR(s, 1, _1(n)) {\n    REP_SS(ss, s) if (!bad[ss]) {\n        if (count_bits(ss)&amp;amp;1) f[s] += f[s^ss];\n        else f[s] -= f[s^ss];\n    }\n}\ncout &amp;lt;&amp;lt; f[_U(n)] * m \/ 2 &amp;lt;&amp;lt; endl;\n<\/code><\/pre>\n\n}\n<\/pre>\n
\u7136\u540e\u53d1\u73b0\u8fd9\u4e2a\u9898\u53ea\u8981\u52a0\u4e2a\u7ef4\u3002\u3002\u3002<\/p>\n
\nconst int N = 15;\n\nInt f[N+2][1&lt;&lt;N], g[N+2][1&lt;&lt;N], fact[N+2];\nbool bad[1&lt;&lt;N]; int adj[1&lt;&lt;N];\nint n, m, k;\n\nstruct Edge {\n    int a, b;\n    void in() {\n        RD(a, b); --a; --b;\n        a = _1(a); b = _1(b);\n        adj[a] |= b;\n    }\n    bool in(int s) {\n        return (s&amp;a)&amp;&amp;(s&amp;b);\n    }\n} E[N*(N-1)\/2];\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\n#endif\n    RD(n, m, k); ++k; REP(i, m) E[i].in();\n    fact[0] = 1; REP_1(i, k) fact[i] = fact[i-1] * i;\n\n<pre><code>FOR(s, 1, _1(n)) {\n    adj[s] |= adj[s^low_bit(s)];\n    REP(i, m) if (E[i].in(s)) {\n        bad[s] = 1;\n        break;\n    }\n}\n\ng[0][0] = 1; REP_1(i, k) FOR(s, 1, _1(n)) {\n    REP_SS(ss, s) if (!bad[ss]) {\n        if (count_bits(ss)&amp;amp;1) g[i][s] += g[i-1][s^ss];\n        else g[i][s] -= g[i-1][s^ss];\n    }\n}\n\nf[0][0] = 1; REP_1(i, k) FOR(s, 1, _1(n)) {\n    REP_1(ii, i) REP_SS(ss, s) if (!(adj[ss^s]&amp;amp;ss)) {\n        Int d = g[ii][ss] * f[i-ii][s^ss];\n        if (ii&amp;amp;1) f[i][s] += d;\n        else f[i][s] -= d;\n    }\n}\nInt z = 0; REP_1(i, k) z += fact[k] \/ fact[k-i] * f[i][_U(n)];\ncout &amp;lt;&amp;lt; z &amp;lt;&amp;lt; endl;\n<\/code><\/pre>\n\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9996\u5148\u4f1a\u505a\u8fd9\u4e2a\u9898\u3002 https:\/\/www.luogu.com.cn\/problem\/P6846 const int N = 18; struct Edge { int a, b; void in() { RD(a, b); –a; –b; a = _1(a); b = _1(b); } bool in(int s) { return (s&amp;a)&amp;&amp;(s&amp;b); } } E[N*N\/2]; Int f[1&lt;&lt;N]; bool bad[1&lt;&lt;N]; int n, m; int main() { #ifndef ONLINE_JUDGE \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin); \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout); #endif […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-3316","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Ru","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=3316"}],"version-history":[{"count":2,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3316\/revisions"}],"predecessor-version":[{"id":3318,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3316\/revisions\/3318"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}