{"id":436,"date":"2018-08-16T14:47:55","date_gmt":"2018-08-16T14:47:55","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=436"},"modified":"2018-08-16T14:47:55","modified_gmt":"2018-08-16T14:47:55","slug":"%e7%89%9b%e5%ae%a2%e5%a4%9a%e6%a0%a1%e7%ac%ac%e4%b9%9d%e5%9c%ba-problem-a-circulant-matrix","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=436","title":{"rendered":"\u725b\u5ba2\u591a\u6821\u7b2c\u4e5d\u573a Problem A Circulant Matrix"},"content":{"rendered":"

\u9898\u610f<\/h2>\n

\u7ed9\u5b9an\u548c a[i] b[i],
\n\u5df2\u77e5FWT(a[i]) * FWT(ans[i]) = FWT(b[i]),\u6c42ans[i]
\n(XOR)<\/p>\n

\u9898\u89e3<\/h2>\n

FWT\u677f\u9898\uff0c\u8d5b\u540e\u5b66\u4e60\u4e86\u4e00\u4e2a<\/p>\n

AC\u4ee3\u7801<\/h2>\n
#include <iostream>\n\nusing namespace std;\nusing ll = long long;\nll MOD = 1e9+7;\nll inv2;\nint n;\n\nconst int maxn = (1 << 20) + 5;\nll a[maxn],b[maxn];\n\nll qpow(ll x, ll y) {\n    ll re = 1;\n    for (; y > 0; y >>= 1) {\n        if (y & 1) {\n            re = re * x % MOD;\n        }\n        x = x * x % MOD;\n    }\n    return re;\n}\n\nvoid FWT_xor(ll *a,int opt)\n{\n    for(int i=1;i<n;i<<=1)\n        for(int p=i<<1,j=0;j<n;j+=p)\n            for(int k=0;k<i;++k)\n            {\n                ll X=a[j+k],Y=a[i+j+k];\n                a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD;\n                if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%MOD,a[i+j+k]=1ll*a[i+j+k]*inv2%MOD;\n            }\n}\n\nint main()\n{\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    inv2 = qpow(2,MOD-2);\n    cin >> n;\n    for(int i = 0;i<n;++i)cin >> a[i];\n    for(int i = 0;i<n;++i)cin >> b[i];\n    FWT_xor(a,1);\n    FWT_xor(b,1);\n    for(int i = 0;i<n;++i) b[i] = b[i] * qpow(a[i],MOD - 2) % MOD;\n    FWT_xor(b,-1);\n    for(int i = 0;i<n;++i) cout << b[i] << \"\\n\";\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u610f \u7ed9\u5b9an\u548c a[i] b[i], \u5df2\u77e5FWT(a[i]) * FWT(ans[i]) = FWT(b[i] […]<\/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,58,40,49,22],"tags":[57],"class_list":["post-436","post","type-post","status-publish","format-standard","hentry","category-c","category-fwt","category-40","category-49","category-22","tag-57"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-72","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/436","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=436"}],"version-history":[{"count":0,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/436\/revisions"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=436"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=436"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=436"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}