{"id":611,"date":"2019-03-20T03:05:24","date_gmt":"2019-03-19T19:05:24","guid":{"rendered":"https:\/\/nike0good.com\/?p=611"},"modified":"2025-02-08T08:27:40","modified_gmt":"2025-02-08T00:27:40","slug":"fwt-dai-ma-bzoj4589hardnim","status":"publish","type":"post","link":"https:\/\/nike0good.com\/?p=611","title":{"rendered":"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim"},"content":{"rendered":"<p>\u9898\u76ee\uff1a\u7ed9n\u4e2a\u4e0d\u8d85\u8fc7m\u7684\u7d20\u6570\uff0c\u6c42xor\u548c=0\u7684\u65b9\u6848\u6570\uff0cFWT\u53d8\u6362\u88f8\u9898\u3002<br \/>\n<a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=4589\">\u9898\u76ee<\/a><\/p>\n<p>2\u5173\u4e8eF\u9006\u5143\u7684\u516c\u5f0f\uff1a $inv(2)=(F+1)&gt;&gt;1$<br \/>\n\u8bc1\uff1a$ [(F+1)&gt;&gt;1]*2 \\pmod F=F+1 \\pmod F =1$ <\/p>\n<p>\u4ee3\u7801\uff1a<\/p>\n<pre><code class=\"language-cpp\">\n#include&lt;bits\/stdc++.h&gt; \nusing namespace std;\n#define For(i,n) for(int i=1;i&lt;=n;i++)\n#define Fork(i,k,n) for(int i=k;i&lt;=n;i++)\n#define Rep(i,n) for(int i=0;i&lt;n;i++)\n#define ForD(i,n) for(int i=n;i;i--)\n#define RepD(i,n) for(int i=n;i&gt;=0;i--)\n#define Forp(x) for(int p=pre[x];p;p=next[p])\n#define Forpiter(x) for(int &amp;p=iter[x];p;p=next[p])  \n#define Lson (o&lt;&lt;1)\n#define Rson ((o&lt;&lt;1)+1)\n#define MEM(a) memset(a,0,sizeof(a));\n#define MEMI(a) memset(a,0x3f,sizeof(a));\n#define MEMi(a) memset(a,128,sizeof(a));\n#define MEMx(a,b) memset(a,b,sizeof(a));\n#define INF (0x3f3f3f3f)\n#define pb push_back\n#define mp make_pair\n#define fi first\n#define se second\n#define vi vector&lt;int&gt; \n#define pi pair&lt;int,int&gt;\n#define SI(a) ((a).size())\n#define Pr(kcase,ans) printf(&quot;Case #%d: %lld\\n&quot;,kcase,ans);\n#define PRi(a,n) For(i,n-1) cout&lt;&lt;a[i]&lt;&lt;&#039; &#039;; cout&lt;&lt;a[n]&lt;&lt;endl;\n#define PRi2D(a,n,m) For(i,n) { \\\n                        For(j,m-1) cout&lt;&lt;a[i][j]&lt;&lt;&#039; &#039;;\\\n                        cout&lt;&lt;a[i][m]&lt;&lt;endl; \\\n                        } \n#pragma comment(linker, &quot;\/STACK:102400000,102400000&quot;)\n#define ALL(x) (x).begin(),(x).end()\ntypedef long long ll;\ntypedef long double ld;\ntypedef unsigned long long ull;\nll F=1000000007LL;\nll iv2=F+1&gt;&gt;1; \/\/\u00d5\u00e2\u00b8\u00f6\u00bc\u00c6\u00cb\u00e3\u00cb\u00bc\u00c2\u00b7\u00ba\u00c3\u00c6\u00c0 \nll mul(ll a,ll b){return (a*b)%F;}\nll add(ll a,ll b){return (a+b)%F;}\nll sub(ll a,ll b){return ((a-b)%F+F)%F;}\nvoid upd(ll &amp;a,ll b){a=(a%F+b%F)%F;}\ninline int read()\n{\n    int x=0,f=1; char ch=getchar();\n    while(!isdigit(ch)) {if (ch==&#039;-&#039;) f=-1; ch=getchar();}\n    while(isdigit(ch)) { x=x*10+ch-&#039;0&#039;; ch=getchar();}\n    return x*f;\n} \nvoid fwt(int*a,int n){\n    int i,j,k,x;\n    for(k=2;k&lt;=n;k&lt;&lt;=1){\n        for(i=0;i&lt;n;i+=k){\n            for(j=i;j&lt;i+(k&gt;&gt;1);j++){\n                x=a[j]+a[j+(k&gt;&gt;1)];if(x&gt;=F) x-=F;\n                a[j]=a[j]-a[j+(k&gt;&gt;1)];if(a[j]&lt;0) a[j]+=F;\n                a[j+(k&gt;&gt;1)]=x;\n            }\n        }\n    }\n}\nvoid twf(int*a,int n){\n    int i,j,k,x;\n    for(k=n;k&gt;=2;k&gt;&gt;=1){\n        for(i=0;i&lt;n;i+=k){\n            for(j=i;j&lt;i+(k&gt;&gt;1);j++){\n                x=a[j]+a[j+(k&gt;&gt;1)];\n                a[j+(k&gt;&gt;1)]=(int)(1LL*(a[j+(k&gt;&gt;1)]-a[j]+F)*iv2%F);\n                a[j]=(int)(1LL*x*iv2%F);\n            }\n        }\n    }\n}\nll pow2(ll a,ll b){\n    if (!b) return 1%F;\n    ll p=pow2(a,b\/2);\n    p=mul(p,p);\n    if (b&amp;1) p=mul(p,a);\n    return p;\n}\n#define MAXN (50000&lt;&lt;3)\nint b[MAXN],a[MAXN];\nll n,m;\nint main()\n{\n\/\/  freopen(&quot;bzoj4589.in&quot;,&quot;r&quot;,stdin);\n\/\/  freopen(&quot;.out&quot;,&quot;w&quot;,stdout);\n\n    n=50000;\n    MEM(b) b[1]=b[0]=1;\n    Fork(i,2,n) if (!b[i]) {\n        for(int j=2;i*j&lt;=n;j++)\n            b[i*j]=1;\n    }   \n    while(cin&gt;&gt;n&gt;&gt;m) {\n        int len=1;\n        while(len&lt;=m) len&lt;&lt;=1;\n        Rep(i,len) a[i]=(!b[i])&amp;&amp;(i&lt;=m);\n        fwt(a,len);\n        Rep(i,len) a[i]=pow2(a[i],n);\n        twf(a,len);\n        printf(&quot;%d\\n&quot;,a[0]);\n    }\n\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\uff1a\u7ed9n\u4e2a\u4e0d\u8d85\u8fc7m\u7684\u7d20\u6570\uff0c\u6c42xor\u548c=0\u7684\u65b9\u6848\u6570\uff0cFWT\u53d8\u6362\u88f8\u9898\u3002 \u9898\u76ee 2\u5173\u4e8eF\u9006\u5143\u7684\u516c\u5f0f\uff1a $inv(2 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","footnotes":""},"categories":[130],"tags":[],"class_list":["post-611","post","type-post","status-publish","format-standard","hentry","category-fwt"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.2 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>FWT\u4ee3\u7801-BZOJ 4589 Hard Nim - nike0good<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/nike0good.com\/?p=611\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim - nike0good\" \/>\n<meta property=\"og:description\" content=\"\u9898\u76ee\uff1a\u7ed9n\u4e2a\u4e0d\u8d85\u8fc7m\u7684\u7d20\u6570\uff0c\u6c42xor\u548c=0\u7684\u65b9\u6848\u6570\uff0cFWT\u53d8\u6362\u88f8\u9898\u3002 \u9898\u76ee 2\u5173\u4e8eF\u9006\u5143\u7684\u516c\u5f0f\uff1a $inv(2 [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/nike0good.com\/?p=611\" \/>\n<meta property=\"og:site_name\" content=\"nike0good\" \/>\n<meta property=\"article:published_time\" content=\"2019-03-19T19:05:24+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-02-08T00:27:40+00:00\" \/>\n<meta name=\"author\" content=\"nike0good\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"nike0good\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=611#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=611\"},\"author\":{\"name\":\"nike0good\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\"},\"headline\":\"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim\",\"datePublished\":\"2019-03-19T19:05:24+00:00\",\"dateModified\":\"2025-02-08T00:27:40+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=611\"},\"wordCount\":21,\"commentCount\":0,\"articleSection\":[\"FWT\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/nike0good.com\\\/?p=611#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=611\",\"url\":\"https:\\\/\\\/nike0good.com\\\/?p=611\",\"name\":\"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim - nike0good\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/#website\"},\"datePublished\":\"2019-03-19T19:05:24+00:00\",\"dateModified\":\"2025-02-08T00:27:40+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=611#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/nike0good.com\\\/?p=611\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=611#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/nike0good.com\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#website\",\"url\":\"https:\\\/\\\/nike0good.com\\\/\",\"name\":\"nike0good\",\"description\":\"\u6709\u6240\u4f5c\u4e3a\u662f\u4eba\u751f\u7684\u6700\u9ad8\u5883\u754c\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/nike0good.com\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\",\"name\":\"nike0good\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"caption\":\"nike0good\"},\"sameAs\":[\"https:\\\/\\\/nike0good.com\"],\"url\":\"https:\\\/\\\/nike0good.com\\\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim - nike0good","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/nike0good.com\/?p=611","og_locale":"zh_CN","og_type":"article","og_title":"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim - nike0good","og_description":"\u9898\u76ee\uff1a\u7ed9n\u4e2a\u4e0d\u8d85\u8fc7m\u7684\u7d20\u6570\uff0c\u6c42xor\u548c=0\u7684\u65b9\u6848\u6570\uff0cFWT\u53d8\u6362\u88f8\u9898\u3002 \u9898\u76ee 2\u5173\u4e8eF\u9006\u5143\u7684\u516c\u5f0f\uff1a $inv(2 [&hellip;]","og_url":"https:\/\/nike0good.com\/?p=611","og_site_name":"nike0good","article_published_time":"2019-03-19T19:05:24+00:00","article_modified_time":"2025-02-08T00:27:40+00:00","author":"nike0good","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"nike0good","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"1 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/nike0good.com\/?p=611#article","isPartOf":{"@id":"https:\/\/nike0good.com\/?p=611"},"author":{"name":"nike0good","@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad"},"headline":"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim","datePublished":"2019-03-19T19:05:24+00:00","dateModified":"2025-02-08T00:27:40+00:00","mainEntityOfPage":{"@id":"https:\/\/nike0good.com\/?p=611"},"wordCount":21,"commentCount":0,"articleSection":["FWT"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/nike0good.com\/?p=611#respond"]}]},{"@type":"WebPage","@id":"https:\/\/nike0good.com\/?p=611","url":"https:\/\/nike0good.com\/?p=611","name":"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim - nike0good","isPartOf":{"@id":"https:\/\/nike0good.com\/#website"},"datePublished":"2019-03-19T19:05:24+00:00","dateModified":"2025-02-08T00:27:40+00:00","author":{"@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad"},"breadcrumb":{"@id":"https:\/\/nike0good.com\/?p=611#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/nike0good.com\/?p=611"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/nike0good.com\/?p=611#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/nike0good.com\/"},{"@type":"ListItem","position":2,"name":"FWT\u4ee3\u7801-BZOJ 4589 Hard Nim"}]},{"@type":"WebSite","@id":"https:\/\/nike0good.com\/#website","url":"https:\/\/nike0good.com\/","name":"nike0good","description":"\u6709\u6240\u4f5c\u4e3a\u662f\u4eba\u751f\u7684\u6700\u9ad8\u5883\u754c","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/nike0good.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad","name":"nike0good","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","caption":"nike0good"},"sameAs":["https:\/\/nike0good.com"],"url":"https:\/\/nike0good.com\/?author=1"}]}},"_links":{"self":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=611"}],"version-history":[{"count":5,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/611\/revisions"}],"predecessor-version":[{"id":656,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/611\/revisions\/656"}],"wp:attachment":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}