zzx<\/code><\/p>\n\n- \n
\u9898\u76ee\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n![\"\"](\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/01\/index.png\")
<\/p>\n
\n- \n
\u8f93\u5165\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n\u7b2c\u4e00\u884c\u4e00\u4e2a\u6b63\u6574\u6570 \\(n\\) \u8868\u793a\u6570\u5bf9\u4e2a\u6570\u3002<\/p>\n
\u63a5\u4e0b\u6765 \\(n\\) \u884c\uff0c\u7b2c \\(i\\) \u884c\u4e24\u4e2a\u6b63\u6574\u6570 \\(a_i, b_i\\)\uff0c\u8868\u793a\u4e00\u4e2a\u6570\u5bf9 \\((a_i, b_i)\\) \u3002<\/p>\n
\n- \n
\u8f93\u51fa\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n\u4e00\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6240\u6c42\u5f0f\u5b50\u7684\u503c\u3002<\/p>\n
\n- \n
\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n3\r\n2 1\r\n2 1\r\n3 2<\/pre>\n
\n- \n
\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n26<\/pre>\n
\n- \n
\u6837\u4f8b\u8bf4\u660e<\/strong><\/h3>\n<\/li>\n<\/ul>\n![\"\"](\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/01\/index-1.png\")
<\/p>\n
\n- \n
\u6570\u636e\u89c4\u6a21\u4e0e\u7ea6\u5b9a<\/strong><\/h3>\n<\/li>\n<\/ul>\n\u4fdd\u8bc1 \\(2 \\leq n \\leq 200,000\\) \uff0c \\(1 \\leq b_i \\leq a_i \\leq 2000\\) \u3002<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
\n <\/p>\n
<\/p>\n
<\/p>\n
\u9996\u5148\u53ef\u4ee5\u5f97\u5230 \\(\\sum\\limits_{i = 1}^n {\\sum\\limits_{j = i + 1}^n {\\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}} = \\frac{1}{2}\\left( {\\sum\\limits_{i = 1}^n {\\sum\\limits_{j = 1}^n {\\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}}} } – \\sum\\limits_{i = 1}^n {\\mbox{C}_{2{a_i}}^{2{b_i}}} } \\right)} } \\) \u3002<\/p>\n
\u53ea\u9700\u8981\u5feb\u901f<\/strong>\u6c42\u51fa \\(\\sum\\limits_{i = 1}^n {\\sum\\limits_{j = 1}^n {\\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}}} } \\) \u3002<\/p>\n\u53d1\u73b0 \\(\\left( {\\begin{array}{*{20}{c}} {0,}&0 \\end{array}} \\right) – \\left( {\\begin{array}{*{20}{c}} {n,}&m \\end{array}} \\right) = \\mbox{C}_{n + m}^m\\) \uff08\u6ce8\uff1a\\(\\left( {\\begin{array}{*{20}{c}} {0,}&0 \\end{array}} \\right) – \\left( {\\begin{array}{*{20}{c}} {n,}&m \\end{array}} \\right)\\) \u4e3a\u4ece \\(\\left( {\\begin{array}{*{20}{c}} {0,}&0 \\end{array}} \\right)\\) \u81f3 \\(\\left( {\\begin{array}{*{20}{c}} {n,}&m \\end{array}} \\right)\\) \u5411\u4e0a\u6216\u5411\u53f3\u8d70\u7684\u8def\u5f84\u603b\u6761\u6570<\/strong>\uff09\uff0c\u56e0\u4e3a\u603b\u5171\u8d70\u4e86 \\(n+m\\) \u4e2a\u5355\u4f4d\u957f\u5ea6\uff0c\u5176\u4e2d\u5206\u522b \\(n\\) \u4e2a\u5355\u4f4d\u957f\u5ea6\u5411\u53f3\u8d70\u4e14 \\(m\\) \u4e2a\u5355\u4f4d\u957f\u5ea6\u5411\u4e0a\u8d70\uff08\\(\\mbox{C}_{n+m}^m=\\mbox{C}_{n+m}^n\\)\uff09\u3002<\/p>\n\u6240\u4ee5 \\(\\begin{array}{c} \\sum\\limits_{i = 1}^n {\\sum\\limits_{j = 1}^n {\\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}}} } = \\left( {\\begin{array}{*{20}{c}} {0,}&0 \\end{array}} \\right) – \\left( {\\begin{array}{*{20}{c}} {{a_i} + {a_j} – {b_i} – {b_j},}&{{b_i} + {b_j}} \\end{array}} \\right)\\\\ = \\left( {\\begin{array}{*{20}{c}} { – {a_j} + {b_j},}&{ – {b_j}} \\end{array}} \\right) ~- \\left( {\\begin{array}{*{20}{c}} {{a_i} – {b_i},}&{{b_i}} \\end{array}} \\right) \\end{array}\\) \u3002<\/p>\n
\u5373\u6c42\u6240\u6709 \\(\\left( {\\begin{array}{*{20}{c}} { – {a_j} + {b_j},}&{ – {b_j}} \\end{array}} \\right)\\) \u81f3\u6240\u6709 \\(\\left( {\\begin{array}{*{20}{c}} {{a_i} – {b_i},}&{{b_i}} \\end{array}} \\right)\\) \u7684\u8def\u5f84\u603b\u6761\u6570\uff0c\u56e0\u4e3a\u5de6\u8fb9\u53f3\u8fb9\u5206\u522b\u53ea\u4e0e \\(i, j\\) \u6709\u5173<\/strong>\uff0c\u6240\u4ee5\u7b80\u5355DP\u5373\u53ef\u3002<\/p>\n\u8bbe \\(f_{i, j}\\) \u4e3a\u4ece\u53f3\u4e0a\u89d2\u6240\u6709\u51fa\u53d1\u70b9<\/strong>\u5411\u5de6\u4e0b\u65b9\u8d70\u5230 \\((i, j)\\) \u65f6\u7684\u8def\u5f84\u603b\u6761\u6570\u3002\u663e\u7136\uff0c\u5f53\u524d \\(\\left( {\\begin{array}{*{20}{c}} {i,}&{j} \\end{array}} \\right)\\) \u7b49\u4e8e\u67d0\u4e2a \\(\\left( {\\begin{array}{*{20}{c}} {{a_k} – {b_k},}&{{b_k}} \\end{array}} \\right)\\) \u65f6\uff0c\u90a3\u4e48\u8def\u5f84\u6761\u6570\u8981 \\(+1\\) \uff0c\u5426\u5219\u4e0d\u7528\uff0c\u5373 \\(f_{i, j}=f_{i+1, j}+f_{i, j+1}+mpos\\left( {\\begin{array}{*{20}{c}} {i,}&{j} \\end{array}} \\right)\\) \uff0c \\(mpos\\left( {\\begin{array}{*{20}{c}} {x,}&{y} \\end{array}} \\right)\\) \u8868\u793a\u6709\u51e0\u4e2a \\(\\left( {\\begin{array}{*{20}{c}} {{a_k} – {b_k},}&{{b_k}} \\end{array}} \\right)\\) \u7b49\u4e8e \\(\\left( {\\begin{array}{*{20}{c}} {x,}&{y} \\end{array}} \\right)\\) \uff08\u76f8\u5f53\u4e8eDP\u7684\u521d\u59cb\u503c\uff09\u3002\u5f53\u9047\u5230 \\(\\left( {\\begin{array}{*{20}{c}} { – {a_k} + {b_k},}&{ – {b_k}} \\end{array}} \\right)\\) \u65f6\u76f4\u63a5\u8d21\u732e\u7b54\u6848\u5373\u53ef\u3002<\/p>\n\u6700\u540e\u522b\u5fd8\u4e86\u51cf\u53bb \\({\\sum\\limits_{i = 1}^n {\\mbox{C}_{2{a_i}}^{2{b_i}}} }\\) \uff0c\u9664\u4ee5 \\(2\\) \u5176\u5b9e\u5e76\u4e0d\u9700\u8981\u9006\u5143\u3002<\/p>\n
\u56e0\u4e3a\u5750\u6807\u6709\u7684\u4e3a\u8d1f\uff0c\u8bb0\u5f97\u6570\u7ec4\u4e0b\u6807\u6574\u4f53\u504f\u79fb\u3002<\/p>\n
<\/p>\n
#include <cstdio>\r\n#include <cstdlib>\r\n#include <cstring>\r\n#include <climits>\r\n\r\n#define _max(_a,_b) ((_a)>(_b)?(_a):(_b))\r\n\r\n#define MOD 1000000007\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=getchar();\r\n\twhile(!(c>='0' && c<='9'))\r\n\t\tc=getchar();\r\n\tregister int a=0;\r\n\twhile(c>='0' && c<='9')\r\n\t{\r\n\t\ta*=10;a+=c-'0';\r\n\t\tc=getchar();\r\n\t}\r\n\treturn a;\r\n}\r\n\r\nint a[205050],b[205050];\r\nint c[4050][4050];\r\n\/\/ c[a][b] (a>b);\r\nint _f[4050][4050],_wpos[4050][4050],_apos[4050][4050];\r\n#define _getpos(k,_a,_b) (k[_a+2005][_b+2005])\r\n#define f(_a,_b) (_getpos(_f,_a,_b))\r\n#define wpos(_a,_b) (_getpos(_wpos,_a,_b))\r\n#define apos(_a,_b) (_getpos(_apos,_a,_b))\r\n\r\nint main()\r\n{\r\n\tregister int N=getnum();\r\n\tregister int rmx=0,lmx=0,amx=0;\r\n\tfor(register int i=1;i<=N;i++)\r\n\t{\r\n\t\ta[i]=getnum(),b[i]=getnum();\r\n\t\twpos(a[i]-b[i],b[i])++;\r\n\t\tapos(b[i]-a[i],-b[i])++;\r\n\t\trmx=_max(rmx,a[i]-b[i]);\r\n\t\tlmx=_max(lmx,b[i]);\r\n\t\tamx=_max(amx,a[i]);\r\n\t}\r\n\t\r\n\tregister int ans=0;\r\n\tfor(register int i=rmx;i>=-rmx;i--)\r\n\t\tfor(register int j=lmx;j>=-lmx;j--)\r\n\t\t{\r\n\t\t\tf(i,j)=(f(i,j+1)+f(i+1,j)+wpos(i,j))%MOD;\r\n\t\t\tif(apos(i,j))\r\n\t\t\t\tans=(ans+(long long)apos(i,j)*f(i,j)%MOD)%MOD;\r\n\t\t}\r\n\t\r\n\tamx<<=1;\r\n\tc[0][0]=1;\r\n\tfor(register int i=1;i<=amx;i++)\r\n\t{\r\n\t\tc[i][0]=c[i][i]=1;\r\n\t\tfor(register int j=1;j<i;j++)\r\n\t\t\tc[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;\r\n\t}\r\n\t\r\n\tregister int tmns=0;\r\n\tfor(register int i=1;i<=N;i++)\r\n\t\ttmns=(tmns+c[a[i]<<1][b[i]<<1])%MOD;\r\n\t\r\n\tregister int rans=ans-tmns;\r\n\t(rans<0?rans+=MOD:0);\r\n\t(rans%2==0?rans\/=2:(rans+=MOD)\/=2);\r\n\tprintf(\"%d\\n\",rans);\r\n\t\r\n\treturn 0;\r\n}<\/pre>\n <\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"