{"id":301,"date":"2024-03-26T17:07:23","date_gmt":"2024-03-26T09:07:23","guid":{"rendered":"https:\/\/linxce.ink\/?p=301"},"modified":"2024-03-26T17:08:04","modified_gmt":"2024-03-26T09:08:04","slug":"agc016f-games-on-dag%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/linxce.ink\/index.php\/agc016f-games-on-dag%e9%a2%98%e8%a7%a3\/%e5%85%a8%e9%83%a8\/acm\/%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92\/","title":{"rendered":"[AGC016F] Games on DAG\u9898\u89e3"},"content":{"rendered":"<p>\u4f8b\u9898\u2160\uff1a<\/p>\n<blockquote>\n<p><img decoding=\"async\" src=\"https:\/\/linxce.ink\/wp-content\/uploads\/2024\/03\/image-20240325205504707.png\" alt=\"\" \/><\/p>\n<\/blockquote>\n<p>\u9898\u89e3\uff1a\u65f6\u95f4\u590d\u6742\u5ea6 O(n*3^n)<\/p>\n<blockquote>\n<p><img decoding=\"async\" src=\"https:\/\/linxce.ink\/wp-content\/uploads\/2024\/03\/image-20240325210242431.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/linxce.ink\/wp-content\/uploads\/2024\/03\/image-20240326165812238.png\" alt=\"\" \/><\/p>\n<\/blockquote>\n<pre><code class=\"language-cc\">int n, m, a[N][N]; \/\/ \u90bb\u63a5\u77e9\u9635\nint twoP[N * N], dp[1 &lt;&lt; N], cnt[1 &lt;&lt; N][N];\n\/\/ dp[I]\u8bb0\u5f55\u96c6\u5408I\u5728\u5fc5\u8d25\u7684\u524d\u63d0\u4e0b\u6240\u6709\u7684\u8fb9\u7ec4\u5408\u65b9\u5f0f, cnt[i][j]\u8bb0\u5f55j\u5230\u96c6\u5408i\u7684\u8fb9\u6570\nvoid solve()\n{\n    cin &gt;&gt; n &gt;&gt; m;\n    twoP[0] = 1;\n    for (int i = 1; i &lt;= m; ++i)\n        twoP[i] = 2 * twoP[i - 1] % mod;\n    for (int i = 1, x, y; i &lt;= m; ++i)\n    {\n        cin &gt;&gt; x &gt;&gt; y;\n        a[x][y] = 1;\n    }\n    for (int U = 1; U &lt; 1 &lt;&lt; n; ++U)\n    {\n        int j = __builtin_ffs(U) - 1; \/\/ \u6700\u540e\u4e00\u4f4d1\u7684\u4f4d\u7f6e\n        for (int u = 0; u &lt;= n; ++u)  \/\/ \u9884\u5904\u7406cnt\n            cnt[U][u] = cnt[U ^ 1 &lt;&lt; j][u] + a[u + 1][j + 1];\n    }\n    for (int U = 0; U &lt; 1 &lt;&lt; n; ++U) \/\/ \u679a\u4e3e\u5168\u96c6\u5b50\u96c6U\n    {\n        if((u &amp; 3) != 3 &amp;&amp; (u &amp; 3) != 0) continue;\n        dp[U] = 1; \/\/ \u521d\u59cb\u5316\u96c6\u5408U\u5fc5\u8d25\u6001\u7684\u603b\u6570\n        for (int T = U &amp; (U - 1); T; --T &amp;= U) \/\/ \u679a\u4e3eU\u7684\u5b50\u96c6T\n        {\n            if ((T &amp; 1) != (T &gt;&gt; 1 &amp; 1)) \/\/ 1,2\u90fd\u5728\u6216\u90fd\u4e0d\u5728T\n                continue;\n            int S = U ^ T, coef = 1; \/\/ S\u662fU - T\n            for (int i = 0; i &lt; n; ++i)\n            {\n                if (T &gt;&gt; i &amp; 1)\n                    coef = (ll)coef * twoP[cnt[S][i]] % mod; \/\/ T\u5230S\u968f\u4fbf\u9009\u8fb9\n                if (S &gt;&gt; i &amp; 1)\n                    coef = (ll)coef * (twoP[cnt[T][i]] - 1) % mod; \/\/ S\u5230T\u81f3\u5c11\u9009\u4e00\u6761\u8fb9\n            }\n            \/\/dp[T]\u5185\u90e8\u6ca1\u6709\u8fb9,\u53ea\u6709\u7a7a\u96c6\u4e00\u79cd\u60c5\u51b5\n            dp[U] = (dp[U] + (ll)coef * dp[S] % mod) % mod;\n        }\n    }\n    cout &lt;&lt; (twoP[m] - dp[(1 &lt;&lt; n) - 1] + mod) % mod &lt;&lt; endl;\n}<\/code><\/pre>\n<blockquote><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>\u4f8b\u9898\u2160\uff1a \u9898\u89e3\uff1a\u65f6\u95f4\u590d\u6742\u5ea6 O(&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[28,30,29],"tags":[32,31,33,15],"class_list":["post-301","post","type-post","status-publish","format-standard","hentry","category-28","category-30","category-dp","tag-sg","tag-dp","tag-33","tag-15"],"_links":{"self":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/301","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/comments?post=301"}],"version-history":[{"count":2,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/301\/revisions"}],"predecessor-version":[{"id":306,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/301\/revisions\/306"}],"wp:attachment":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/media?parent=301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/categories?post=301"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/tags?post=301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}