{"id":547,"date":"2018-12-31T20:07:30","date_gmt":"2018-12-31T12:07:30","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=547"},"modified":"2018-12-31T20:07:30","modified_gmt":"2018-12-31T12:07:30","slug":"cf1091-good-bye-2018","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/31\/cf1091-good-bye-2018\/","title":{"rendered":"CF1091 Good Bye 2018"},"content":{"rendered":"\n

\u4e0d\u77e5\u4e0d\u89c9\u5c31\u5230\u4e862018\u7684\u6700\u540e\u4e00\u5929\u3002\u8fd9\u4e2a\u535a\u5ba2\u4e5f\u6709\u4e24\u4e2a\u591a\u6708\u4e86\u3002
\u6211\u7684\u59ff\u52bf\u6c34\u5e73\u56fa\u7136\u6709\u4e86\u4e00\u5b9a\u957f\u8fdb\uff0c\u4f46\u548c\u5de8\u795e\u7684\u8ddd\u79bb\u5374\u662f\u8d8a\u62c9\u8d8a\u8fdc\u4e86\u3002
\u8fd9\u573aCF\u4e5f\u662f\uff0c\u624b\u901f\u573a\u6211\u5374\u6ca1\u80fd\u6709\u8db3\u591f\u7684\u624b\u901f\u3002\u5c24\u5176\u662fD\u9898\u90a3\u79cd\u8d85\u7b80\u5355\u7684\u9898\u76ee\u5374\u6b7b\u78d5\u4e86\u534a\u5929\u624d\u78d5\u51fa\u6765\uff0cF\u4e5f\u6ca1\u505a\u51fa\u6765\u3002
\u603b\u4e4b\uff0c\u795d\u5927\u5bb6\u65b0\u5e74\u5feb\u4e50_(:\u0437\u300d\u2220)_
<\/p>\n\n\n\n

\n\n\n\n

CF1091A
\n\u4f9d\u9898\u610f\u5373\u53ef\u3002
\n\u5343\u4e07\u522b\u6389\u8fdb\u5206\u7c7b\u8ba8\u8bba\u7684\u5751\u91cc\u3002<\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\nint a,b,c;\n\nvoid init(){\n\tscanf(\"%d%d%d\",&a,&b,&c);\n\t--b,c-=2;\n\tprintf(\"%d\",min(min(a,b),c)*3+3);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1091B
\n\u6211\u4eec\u5c06\u6bcf\u4e2a\u5b9d\u85cf\u90fd\u52a0\u4e0a\u6bcf\u4e00\u4e2a\u5411\u91cf\u7bad\u5934\uff0c\u5e76\u6807\u8bb0\u76ee\u7684\u5730\u3002
\n\u7b54\u6848\u662f\u4efb\u610f\u4e00\u4e2a\u88ab\u6807\u8bb0n\u6b21\u7684\u3002
\n\u53ef\u4ee5\u7528map\u6216\u8005hashmap\u7ef4\u62a4\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\n#include<map>\nusing namespace std;\nint a[1005],b[1005],c[1005],d[1005];\ntypedef pair<int,int> pii;\ntypedef map<pii,int> mppii;\nmppii mp;\nint n;\nvoid init(){\n\tscanf(\"%d\",&n);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d%d\",a+i,b+i);\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d%d\",c+i,d+i);\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tfor(int j=1;j<=n;++j){\n\t\t\tpii nw(a[i]+c[j],b[i]+d[j]);\n\t\t\t++mp[nw];\n\t\t}\n\t}\n\tmppii::iterator it=mp.begin();\n\twhile(it!=mp.end()){\n\t\tif(it->second==n){\n\t\t\tprintf(\"%d %d\\n\",it->first.first,it->first.second);\n\t\t\tbreak;\n\t\t}\n\t\t++it;\n\t} \n}\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1091C
\n\u89c2\u5bdf\u9898\u610f\u4ee5\u540e\u6211\u4eec\u53d1\u73b0\uff0c\u5bf9\u4e8e\\(k\\)\uff0c\u5f53\u4e14\u4ec5\u5f53\\(n\\%k == 0\\)\u7684\u65f6\u5019\uff0c\\(k\\)\u4f1a\u548c\u5176\u4ed6\u7684\u672c\u8d28\u4e0d\u540c\u3002
\n\u4f9d\u636e\u5269\u4f59\u7cfb\u7684\u6027\u8d28\u5bb9\u6613\u8bc1\u660e\u3002
\n\u90a3\u4e48\u6211\u4eec\u5c31\u5f97\u5230\u4e86\u4e00\u4e2a\u6734\u7d20\u7684\u6c42\u7b54\u6848\u516c\u5f0f\uff1a
\n$$\\forall x,st:n\\% x==0,ans_{x}=\\sum_{i=0}^{n\/gcd(n,x)-1}(1+(ix-1)\\%n+1) $$
\n\u7136\u540e\u8003\u8651\u5230\\(n\\%x==0\\)\uff0c\u6240\u4ee5
\n$$ans_{x}=\\sum_{i=0}^{n\/gcd(n,x)-1}(1+(ix-1)\\%n)==\\sum_{i=0}^{n\/gcd(n,x)-1}(1+ix)$$
\n\u5957\u4e0a\u7b49\u5dee\u6570\u5217\u6c42\u548c\u516c\u5f0f\u5373\u53ef\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\ninline long long gcd(long long A,long long B){\n\treturn B?gcd(B,A%B):A;\n}\nlong long n;\nlong long ans[100005],tp=0;\n\ninline void calc(int X){\n\tlong long tms=n\/gcd(n,X);\n\tans[++tp]=tms+((((tms*(tms-1))>>1)*X));\n}\n\nvoid init(){\n\tscanf(\"%I64d\",&n);\n\tfor(int i=1;i*i<=n;++i){\n\t\tif(!(n%i)){\n\t\t\tcalc(i);\n\t\t\tif(i*i!=n){\n\t\t\t\tcalc(n\/i);\n\t\t\t}\n\t\t}\n\t}\n\tsort(ans+1,ans+1+tp);\n\ttp=unique(ans+1,ans+1+tp)-1-ans;\n\tfor(int i=1;i<=tp;++i){\n\t\tprintf(\"%I64d \",ans[i]);\n\t}\n}\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1091D
\n\u7531\u4e8e\u957f\u5ea6\u4e3a\\(n\\)\uff0c\u663e\u7136\u5e8f\u5217\u7684\u503c\u5fc5\u7136\u662f\\(\\frac{(n*(n+1))}{2}-SUM_i+SUM_{i+1}\\), \u5176\u4e2d\\(SUM_{i}\\)\u8868\u793a\u7b2c\\(i\\)\u4e2a\u6392\u5217\u7684\u67d0\u4e2a\u524d\u7f00\u548c\u3002 
\n\u53c8\u6392\u5217\u7684\u6027\u8d28\u6211\u4eec\u4f1a\u53d1\u73b0\uff0c\u5bf9\u4e8e\u4efb\u610f\u4e24\u4e2a\u76f8\u90bb\u7684\u5168\u6392\u5217\uff0c\u5b83\u7684\u4efb\u610f\u957f\u5ea6\u524d\u7f00\u548c\u8981\u4e48\u589e\u52a0\u4e14\u524d\u7f00\u5e8f\u5217\u53d8\u5316\uff0c\u8981\u4e48\u524d\u7f00\u548c\u4fdd\u6301\u4e0d\u53d8\u4e14\u524d\u7f00\u5e8f\u5217\u4fdd\u6301\u4e0d\u53d8\u3002
\n\u6545\u800c\uff0c\u5982\u679c\u4e00\u4e2a\u5e8f\u5217\u8981\u6ee1\u8db3\u8981\u6c42\uff0c\u5b83\u53ea\u6709\u4e24\u79cd\u60c5\u51b5\u2014\u2014\u5b83\u672c\u8eab\u5c31\u662f\u4e00\u4e2a\u6392\u5217\uff0c\u6216\u8005\u5b83\u6a2a\u8de8\u7684\u4e24\u4e2a\u6392\u5217\u5fc5\u7136\u6709\u4e00\u90e8\u5206\u524d\u7f00\u76f8\u540c\u3002
\n\u5bf9\u4e8e\u7b2c\u4e00\u79cd\u60c5\u51b5\u6211\u4eec\u53ef\u4ee5\u770b\u6210\u5b83\u4eec\u7684\u524d\u7f00\u6709\\(0\\)\u4e2a\u76f8\u540c\u7684\u3002
\n\u95ee\u9898\u8f6c\u5316\u4e3a\u4e86\uff0c\u6c42\u6240\u6709\u6392\u5217\u4e2d\uff0c\u4e24\u79cd\u76f8\u90bb\u6392\u5217\u524d\u7f00\u76f8\u540c\u7684\u957f\u5ea6\u7684\u548c\u3002
\n\u901a\u8fc7\u6253\u8868\u627e\u89c4\u5f8b\uff0c\u6216\u8005\u5bf9\u5168\u6392\u5217\u6027\u8d28\u7684\u7cbe\u786e\u63a8\u6f14\uff0c\u6211\u4eec\u5f97\u5230\u4e86\u8fd9\u6837\u4e00\u4e2a\u6c42\u548c\u5f0f\uff1a
\n$$ ans=\\sum_{pre=0}^{n-2}(n!-(\\Pi_{i=n}^{n-pre+1}i))$$
\n\u4f46\u662f\u66b4\u529b\u8ba1\u7b97\u7684\u590d\u6742\u5ea6\u6700\u574f\u662f\\(n^2\\)\u7684\uff0c\u4ecd\u7136\u65e0\u6cd5\u901a\u8fc7\u6b64\u9898\u3002
\n\u6211\u4eec\u8003\u8651\u4f18\u5316\u8fd9\u4e2a\u6c42\u548c\u3002\u4f18\u5316\u7684\u70b9\u5728\u4e8e\\(\\Pi_{i=n}^{n-pre+1}i\\)\uff0c\u6211\u4eec\uff08\u6beb\u4e0d\uff09\u60ca\u8bb6\u5730\u53d1\u73b0\uff0c\u5b83\u7b49\u4ef7\u4e8e\\(\\frac{n!}{n-pre}\\)\uff0c\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u9884\u5904\u7406\u9636\u4e58\u548c\u9636\u4e58\u7684\u9006\u5143\u3002
\n\u8fd9\u6837\u5c31\u505a\u5b8c\u4e86\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\nconst long long MOD=998244353;\n\nlong long fac[1000005],inv[1000005];\nlong long n;\n\nvoid init(){\n\tscanf(\"%I64d\",&n);\n\tfac[0]=fac[1]=inv[0]=inv[1]=1;\n\tfor(int i=2;i<=n;++i){\n\t\tfac[i]=fac[i-1]*i%MOD;\n\t\tinv[i]=(MOD-MOD\/i)*inv[MOD%i]%MOD;\n\t}\n\tfor(int i=2;i<=n;++i){\n\t\tinv[i]=inv[i-1]*inv[i]%MOD;\n\t}\n\tlong long ans=fac[n];\n\tfor(int i=1;i<=n-2;++i){\n\t\tans+=(fac[n]-fac[n]*inv[n-i]%MOD+MOD)%MOD;\n\t\tans%=MOD;\n\t}\n\tprintf(\"%I64d\",ans);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u4e0d\u77e5\u4e0d\u89c9\u5c31\u5230\u4e862018\u7684\u6700\u540e\u4e00\u5929\u3002\u8fd9\u4e2a\u535a\u5ba2\u4e5f\u6709\u4e24\u4e2a\u591a\u6708\u4e86\u3002\u6211\u7684\u59ff\u52bf\u6c34\u5e73\u56fa\u7136\u6709\u4e86\u4e00\u5b9a\u957f\u8fdb\uff0c\u4f46\u548c\u5de8\u795e\u7684\u8ddd\u79bb\u5374\u662f\u8d8a\u62c9 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cCF1091 Good Bye 2018\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20,24,27,6,59,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/547"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=547"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/547\/revisions"}],"predecessor-version":[{"id":548,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/547\/revisions\/548"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=547"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=547"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=547"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}