{"id":795,"date":"2013-10-05T04:56:25","date_gmt":"2013-10-04T20:56:25","guid":{"rendered":"http:\/\/comzyh.tk\/blog\/?p=795"},"modified":"2013-10-05T05:02:33","modified_gmt":"2013-10-04T21:02:33","slug":"%e7%ad%89%e6%af%94%e6%95%b0%e5%88%97%e6%b1%82%e5%92%8c%e7%9a%84%e4%ba%8c%e5%88%86%e6%b3%95","status":"publish","type":"post","link":"https:\/\/comzyh.com\/blog\/archives\/795\/","title":{"rendered":"\u7b49\u6bd4\u6570\u5217\u6c42\u548c\u7684\u4e8c\u5206\u6cd5"},"content":{"rendered":"

\u5e38\u89c1\u95ee\u9898:\u7ed9\u5b9a\u6574\u6570M,\u7b49\u6bd4\u6570\u5217\\(\\{{a_n}\\}\\),\u6c42\u5176\u524dn\u9879\u548c\u5bf9M\u7684\u6a21<\/p>\n

\u6734\u7d20\u7684\u60f3\u6cd5,\u6211\u4eec\u53ef\u4ee5\u7528\u7b49\u6bd4\u6570\u5217\u6c42\u548c\u516c\u5f0f\\(S_n=\\frac {a_1(1-q^n)}{1-q}\\)\u6c42\u5f97\u548c\u518d\u6a21\u9664M,\u4f46\u662f\u8ba1\u7b97\u8fc7\u7a0b\u4e2d\u53d6\u6a21\u5bfc\u81f4\u5206\u6bcd\u4e0b\u9762\u76841-q\u4e0d\u80fd\u76f4\u63a5\u9664,\u8981\u6c421-q\u7684\u4e58\u6cd5\u9006\u5143;<\/p>\n

\u8fd9\u91cc\u4ecb\u7ecd\u53e6\u4e00\u79cd\u601d\u8def,\u5c31\u662f\u4f7f\u7528\u4e8c\u5206\u7684\u601d\u60f3,\u5f88\u50cf\u77e9\u9635\u5feb\u901f\u5e42
\n\u9996\u5148,\u6211\u4eec\u5148\u8ba8\u8bba\u4e00\u4e2a\u7b80\u5355\u7684\u95ee\u9898:
\n\u6c42\\(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8\\)\u7684\u548c
\n\u63d0\u53d6\u516c\u56e0\u5f0f,\u6211\u4eec\u80fd\u628a\u539f\u5f0f\u53d8\u4e3a
\n\\((a^1+a^2+a^3+a^4)(1+a^4)\\)
\n\u8fdb\u4e00\u6b65\u53d8\u6362\u4e3a\\((a^1+a^2)(1+a^2)(1+a^4)\\)
\n\\(=a(a+a^1)(1+a^2)(1+a^4)\\)
\n\u6211\u4eec\u628a\u8fd9\u79cd\u7b49\u6bd4\u6570\u5217\u524d\\(2^k\\)\u9879\u548c\u8bb0\u4e3a\\(S(k)\\)\u6709\u9012\u63a8\u5f0f\\(S(k)=S(k-1)(1+a^{2^{k-1}})\\)
\n\u8fd9\u662f\u4e8c\u5206\u6cd5\u7684\u5173\u952e,\u4e5f\u5c31\u662f\u8bf4\u6211\u4eec\u80fd\u5728log(n)\u7684\u65f6\u95f4\u5185\u6c42\u51fa\u7b49\u6bd4\u6570\u5217\u524d\\(2^k\\)\u9879\u7684\u548c<\/p>\n

\u5f53\u6211\u4eec\u8981\u6c42\u7684\u4e0d\u662f\u524d2\u7684\u6574\u6570\u6b21\u5e42\u7684\u65f6\u5019,\u6211\u4eec\u5c06n\u5206\u89e3\u4e3a2\u7684\u6574\u6b21\u5e42\u7684\u548c:
\n\u6bd4\u5982\u6c42\u524d\u7b49\u6bd4\u6570\u521711\u9879\u7684\u548c,\u6211\u4eec\u5c0611(\u4e8c\u8fdb\u5236\u8868\u793a:1011)\u5206\u89e3\u4e3a1+2+8(\u4e8c\u8fdb\u5236\u8868\u793a1+10+1000)
\n\u524d11\u9879\u7684\u548c\u53ef\u4ee5\u8868\u793a\u4e3a:
\n\\((a^1)+(a^2+a^3)+(a^4+a^5+a^6+a^7+a^8+a^9+a^{10}+a^{11})\\)
\n\u53ef\u8fdb\u4e00\u6b65\u8868\u793a\u4e3a
\n\\(a^0(a^1)+a^1(a^1+a^2)+a^3(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8)\\)
\n\u5373:\\(a^0S(0)+a^1S(1)+a^3S(3)\\)
\nWell done!\u6211\u4eec\u53c8\u628a\u539f\u5f0f\u5206\u89e3\u6210\u4e86\u591a\u4e2a\\(a^xS(y)\\)\u7684\u548c
\n
\n\u5728\u8fd9\u91cc\u53ef\u80fd\u53ef\u80fd\u4f1a\u6709\u4e00\u4e2a\u5c0f\u5c0f\u7684\u7591\u95ee,\u5c31\u662f\\(a^xS(y)\\)\u4e2d\u7684x\u548cy\u662f\u600e\u4e48\u786e\u5b9a\u7684,\u8fd9\u91cc\u6211\u662f\u53c2\u8003\u7684\u77e9\u9635\u5feb\u901f\u5e42\u7684\u601d\u60f3,x\u5c31\u662f\u5df2\u7ecf\u5904\u7406\u7684\u6307\u6570\u7684\u548c,y\u6839\u636e\u5f53\u524d\u5904\u7406\u7684\u6bd4\u7279\u4f4d\u7f6e\u51b3\u5b9a
\n\u4e00\u4e2a\u5feb\u901f\u5e42\u5927\u6982\u8fd9\u4e48\u5199<\/p>\n

\r\nint pow(int a,int b)\r\n{\r\n    int ans=1,power=a;\r\n    while (b)\r\n    {\r\n        if (b&1)\r\n            ans*=power;\r\n        power*=power;\r\n        b>>=1;\r\n    }\r\n    return ans;\r\n}\r\n<\/pre>\n
\u6ce8\u610f,\u8fd9\u91cc\u9762\u7684power\u4e00\u76f4\u5145\u5f53\\(a^{2^k}\\)\u7684\u89d2\u8272,\u5728\u7b49\u6bd4\u6570\u5217\u6c42\u548c\u4e2d,\u4ed6\u62c5\u4efb\u7684\u529f\u80fd\u8fd8\u5305\u62ec\u63d0\u4f9b\\(S(k)=S(k-1)(1+a^{2^{k-1}})\\)\u4e2d\u7684\\(2^{k-1}\\)
\n\u4e0b\u9762\u662f\u5b8c\u6574\u7684\u6837\u4f8b\u7a0b\u5e8f:<\/p>\n
\r\n\/\/\u7b49\u6bd4\u6570\u5217\u6c42\u548c\r\n\/\/author:comzyh\r\n#include \r\nconst int MOD=9901;\r\nint A,B;\r\nint sum(int n,long long k)\r\n{\r\n    n%=MOD;\r\n    int ans=0;\r\n    int power=n;\r\n    int powersum=n;\/\/S(y)\r\n    int mul=1;\/\/a^x\r\n    while (k)\r\n    {\r\n        if (k&1)\r\n        {\r\n            ans+=mul*powersum;  ans%=MOD;\r\n            mul*=power;         mul%=MOD;\r\n        }\r\n        powersum*=(power+1);    powersum%=MOD;\r\n        power*=power;           power%=MOD;\r\n        k>>=1;\r\n    }\r\n    return ans;\r\n}\r\nint main()\r\n{\r\n    int n,k;\r\n    while (scanf(\"%d%d\",&n,&k)!=EOF)\r\n    {\r\n        printf(\"%d\\n\",sum(n,k));\r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5e38\u89c1\u95ee\u9898:\u7ed9\u5b9a\u6574\u6570M,\u7b49\u6bd4\u6570\u5217,\u6c42\u5176\u524dn\u9879\u548c\u5bf9M\u7684\u6a21 \u6734\u7d20\u7684\u60f3\u6cd5,\u6211\u4eec\u53ef\u4ee5\u7528\u7b49\u6bd4\u6570\u5217\u6c42\u548c\u516c\u5f0f\u6c42\u5f97\u548c\u518d\u6a21\u9664M,\u4f46 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[11,9],"tags":[],"class_list":["post-795","post","type-post","status-publish","format-standard","hentry","category-programing","category-9"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t