{"id":34,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-10\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-10","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-10\/","title":{"rendered":"2020-08-10"},"content":{"rendered":"<p><svg  style=\"display: none;\">\n                        <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path>\n                    <\/svg><\/p>\n<p><a href=\"http:\/\/icpc.upc.edu.cn\/problem.php?id=14581\">http:\/\/icpc.upc.edu.cn\/problem.php?id=14581<\/a><\/p>\n<h5><a id=\"_1\"><\/a>\u9898\u76ee<\/h5>\n<p>14581: Knight<\/p>\n<h5><a id=\"_3\"><\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n<p>There is a knight &#8211; the chess piece &#8211; at the origin (0,0) of a two-dimensional grid.<br \/> When the knight is at the square (i,j), it can be moved to either (i+1,j+2) or (i+2,j+1).<br \/> In how many ways can the knight reach the square (X,Y)?<br \/> Find the number of ways modulo 109+7.<\/p>\n<p>Constraints<br \/> \u00b71\u2264X\u2264106<br \/> \u00b71\u2264Y\u2264106<br \/> \u00b7All values in input are integers.<\/p>\n<h5><a id=\"_13\"><\/a>\u8f93\u5165<\/h5>\n<p>Input is given from Standard Input in the following format:<\/p>\n<p>X Y<\/p>\n<h5><a id=\"_18\"><\/a>\u8f93\u51fa<\/h5>\n<p>Print the number of ways for the knight to reach (X,Y) from (0,0), modulo 109+7.<\/p>\n<h5><a id=\"_20\"><\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n<p>\u3010\u6837\u4f8b1\u3011<br \/> 3 3<br \/> \u3010\u6837\u4f8b2\u3011<br \/> 2 2<br \/> \u3010\u6837\u4f8b3\u3011<br \/> 999999 999999<\/p>\n<h5><a id=\"_27\"><\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n<p>\u3010\u6837\u4f8b1\u3011<br \/> 2<br \/> \u3010\u6837\u4f8b2\u3011<br \/> 0<br \/> \u3010\u6837\u4f8b3\u3011<br \/> 151840682<\/p>\n<h5><a id=\"_34\"><\/a>\u63d0\u793a<\/h5>\n<p>\u6837\u4f8b1\u89e3\u91ca<br \/> There are two ways: (0,0)\u2192(1,2)\u2192(3,3) and (0,0)\u2192(2,1)\u2192(3,3).<br \/> \u6837\u4f8b2\u89e3\u91ca<br \/> The knight cannot reach (2,2).<br \/> \u6837\u4f8b3\u89e3\u91ca<br \/> Print the number of ways modulo 109+7.<\/p>\n<p>\u9006\u5143\u6c42\u7ec4\u5408\u6570<\/p>\n<pre><code>#include <iostream>\n#include <bits\/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nconst int N=1e9+7;\nlong long int w[2005500]={0};\nlong long int p(long long x,long long y)\n{\n    long long int sum1=1;\n    while(y)\n    {\n        if (y&1)\n            sum1=(sum1*x)%N;\n        y>>=1;\n        x=(x*x)%N;\n    }\n    return sum1%N;\n}\nlong long int c1(long long int x,long long int y)\n{\n    if(x<y)\n        swap(x,y);\n    return w[x]*p(w[x-y]*w[y]%N,N-2)%N;\n}\nint main()\n{\n    register ll a,b;\n    cin>>a>>b;\n    ll y=2*a-b;\n    ll x=2*b-a;\n    if(x%3!=0||y%3!=0||x<0||y<0)\n    {\n        printf(\"0n\");\n        return 0;\n    }\n    x=x\/3;\n    y=y\/3;\n    ll w2=x+y;\n    w[0]=1;\n\tfor(ll i=1;i<=2000500;i++)\n\t\tw[i]=(w[i-1]*i)%N;\n    ll w3=(c1(x,w2)+N)%N;\/\/\u9632\u6b62\u8d1f\u6570\u51fa\u73b0\uff0c\u53d6\u4f59\u65f6\u6ce8\u610f\n    cout<<w3<<endl;\n    return 0;\n}\n<\/code><\/pre>\n<p><a href=\"http:\/\/icpc.upc.edu.cn\/problem.php?id=14625\">http:\/\/icpc.upc.edu.cn\/problem.php?id=14625<\/a><\/p>\n<h5><a id=\"_92\"><\/a>\u9898\u76ee<\/h5>\n<p>14625: Max-Min Sums<\/p>\n<h5><a id=\"_94\"><\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n<p>For a finite set of integers X, let f(X)=maxX\u2212minX.<br \/> Given are N integers A1,\u2026,AN.<br \/> We will choose K of them and let S be the set of the integers chosen. If we distinguish elements with different indices even when their values are the same, there are NCK ways to make this choice. Find the sum of f(S) over all those ways.<br \/> Since the answer can be enormous, print it mod(109+7).<\/p>\n<p>Constraints<br \/> \u00b71\u2264N\u2264105<br \/> \u00b71\u2264K\u2264N<br \/> \u00b7|Ai|\u2264109<\/p>\n<h5><a id=\"_104\"><\/a>\u8f93\u5165<\/h5>\n<p>Input is given from Standard Input in the following format:<\/p>\n<p>N K<br \/> A1 \u2026 AN<\/p>\n<h5><a id=\"_109\"><\/a>\u8f93\u51fa<\/h5>\n<p>Print the answer mod(109+7).<\/p>\n<h5><a id=\"_111\"><\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n<p>\u3010\u6837\u4f8b1\u3011<br \/> 4 2<br \/> 1 1 3 4<br \/> \u3010\u6837\u4f8b2\u3011<br \/> 6 3<br \/> 10 10 10 -10 -10 -10<br \/> \u3010\u6837\u4f8b3\u3011<br \/> 3 1<br \/> 1 1 1<br \/> \u3010\u6837\u4f8b4\u3011<br \/> 10 6<br \/> 1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0<\/p>\n<h5><a id=\"_124\"><\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n<p>\u3010\u6837\u4f8b1\u3011<br \/> 11<br \/> \u3010\u6837\u4f8b2\u3011<br \/> 360<br \/> \u3010\u6837\u4f8b3\u3011<br \/> 0<br \/> \u3010\u6837\u4f8b4\u3011<br \/> 999998537<\/p>\n<h5><a id=\"_133\"><\/a>\u63d0\u793a<\/h5>\n<p>\u6837\u4f8b1\u89e3\u91ca<br \/> There are six ways to choose S: {1,1},{1,3},{1,4},{1,3},{1,4},{3,4} (we distinguish the two<br \/> 1s). The value of f(S) for these choices are 0,2,3,2,3,1, respectively, for the total of 11.<br \/> \u6837\u4f8b2\u89e3\u91ca<br \/> There are 20 ways to choose S. In 18 of them, f(S)=20, and in 2 of them, f(S)=0.<br \/> \u6837\u4f8b4\u89e3\u91ca<br \/> Print the sum mod(109+7).<\/p>\n<p>\u7edf\u8ba1\u6700\u5927\u503c\u51fa\u73b0\u7684\u6b21\u6570\u548c\u6700\u5c0f\u503c\u51fa\u73b0\u7684\u6b21\u6570\uff0c\u6700\u540e\u6c42\u548c\u3002<\/p>\n<pre><code>#include <iostream>\n#include <bits\/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nconst int N=1e9+7;\nlong long int w[2005500]={0};\nll num[100500]={0};\nlong long int p(long long x,long long y)\n{\n    long long int sum1=1;\n    while(y)\n    {\n        if (y&1)\n            sum1=(sum1*x)%N;\n        y>>=1;\n        x=(x*x)%N;\n    }\n    return sum1%N;\n}\nlong long int c1(long long int x,long long int y)\n{\n    if(x<y)\n        swap(x,y);\n    return w[x]*p(w[x-y]*w[y]%N,N-2)%N;\n}\nint main()\n{\n    register ll n,k;\n    scanf(\"%lld%lld\",&#038;n,&#038;k);\n    for(int i=0;i<n;i++)\n        scanf(\"%lld\",&#038;num[i]);\n    sort(num,num+n);\n    w[0]=1;\n\tfor(ll i=1;i<=2000500;i++)\n\t\tw[i]=(w[i-1]*i)%N;\n    ll sum=0;\n    for(ll i=0;i<n-k+1;i++)\n    {\n        sum=(sum+(num[n-i-1]-num[i])%N*c1(n-i-1,k-1)%N)%N;\n    }\n    printf(\"%lldn\",(sum%N+N)%N);\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/icpc.upc.edu.cn\/pr&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-34","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/34","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=34"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/34\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=34"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=34"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}