{"id":419,"date":"2018-08-08T18:23:28","date_gmt":"2018-08-08T18:23:28","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=419"},"modified":"2018-08-08T18:23:28","modified_gmt":"2018-08-08T18:23:28","slug":"hdu-4704-sum-%e6%ac%a7%e6%8b%89%e9%99%8d%e5%b9%82","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=419","title":{"rendered":"HDU 4704 Sum \u6b27\u62c9\u964d\u5e42"},"content":{"rendered":"<h2>\u9898\u89e3<\/h2>\n<blockquote><p>\n  \u5229\u7528\u6570\u5b66\u65b9\u6cd5\u4e2d\u7684\u201c\u9694\u677f\u6cd5\u201d\uff0c\u4e0d\u96be\u77e5\u9053\u7ed3\u679c\u5c31\u662f<br \/>\n  $\\displaystyle\\sum_{k=0}^{n-1}{{n-1}\\choose{k}}$<br \/>\n  \u8fd9\u662f\u4e8c\u9879\u5f0f\u5b9a\u7406\u7684\u5c55\u5f00\u5f0f\u3002\u6240\u4ee5\uff0c\u8fd9\u9053\u9898\u5c31\u8f6c\u6362\u4e3a\u6c42\u89e3$2^{n-1} \\mod (10^9+7)$\n<\/p><\/blockquote>\n<h2>AC\u4ee3\u7801<\/h2>\n<pre><code class=\"language-cpp  line-numbers\">#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\n#include &lt;cstring&gt;\n#include &lt;cmath&gt;\n#include &lt;array&gt;\n\nusing namespace std;\nusing ll = long long;\nconst ll mod = 1e9 + 7;\nstring s;\n\nll quickpow(ll x, ll a) {\n    ll ans = 1;\n    while (a) {\n        if (a &amp; 1)\n            ans = ans * x % mod;\n        x = x * x % mod;\n        a &gt;&gt;= 1;\n    }\n    return ans;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    while (cin &gt;&gt; s) {\n        ll n = 0;\n        for (auto i:s) {\n            n = (n * 10 + i - '0') % (mod - 1);\n        }\n        n = (n - 1 + mod - 1) % (mod - 1) + (mod - 1);\n        cout &lt;&lt; quickpow(2, n) &lt;&lt; '\\n';\n    }\n    return 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u89e3 \u5229\u7528\u6570\u5b66\u65b9\u6cd5\u4e2d\u7684\u201c\u9694\u677f\u6cd5\u201d\uff0c\u4e0d\u96be\u77e5\u9053\u7ed3\u679c\u5c31\u662f $\\displaystyle\\sum_{k=0}^{n-1 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,53,22],"tags":[54,55],"class_list":["post-419","post","type-post","status-publish","format-standard","hentry","category-c","category-53","category-22","tag-54","tag-55"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-6L","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/419","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=419"}],"version-history":[{"count":0,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/419\/revisions"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}