YZOJ P3782 [校内训练20180619]组合数问题
时间限制:1000MS 内存限制:524288KB
难度:\(6.5\) 出题人:zzx
-
题目描述
-
输入格式
第一行一个正整数 \(n\) 表示数对个数。
接下来 \(n\) 行,第 \(i\) 行两个正整数 \(a_i, b_i\),表示一个数对 \((a_i, b_i)\) 。
-
输出格式
一行一个整数,表示所求式子的值。
-
样例输入
1 2 3 4 |
3 2 1 2 1 3 2 |
-
样例输出
1 |
26 |
-
样例说明
-
数据规模与约定
保证 \(2 \leq n \leq 200,000\) , \(1 \leq b_i \leq a_i \leq 2000\) 。
首先可以得到 \(\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)} } \) 。
只需要快速求出 \(\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}} {n,}&m \end{array}} \right) = \mbox{C}_{n + m}^m\) (注:\(\left( {\begin{array}{*{20}{c}} {0,}&0 \end{array}} \right) – \left( {\begin{array}{*{20}{c}} {n,}&m \end{array}} \right)\) 为从 \(\left( {\begin{array}{*{20}{c}} {0,}&0 \end{array}} \right)\) 至 \(\left( {\begin{array}{*{20}{c}} {n,}&m \end{array}} \right)\) 向上或向右走的路径总条数),因为总共走了 \(n+m\) 个单位长度,其中分别 \(n\) 个单位长度向右走且 \(m\) 个单位长度向上走(\(\mbox{C}_{n+m}^m=\mbox{C}_{n+m}^n\))。
所以 \(\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}\) 。
即求所有 \(\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)\) 的路径总条数,因为左边右边分别只与 \(i, j\) 有关,所以简单DP即可。
设 \(f_{i, j}\) 为从右上角所有出发点向左下方走到 \((i, j)\) 时的路径总条数。显然,当前 \(\left( {\begin{array}{*{20}{c}} {i,}&{j} \end{array}} \right)\) 等于某个 \(\left( {\begin{array}{*{20}{c}} {{a_k} – {b_k},}&{{b_k}} \end{array}} \right)\) 时,那么路径条数要 \(+1\) ,否则不用,即 \(f_{i, j}=f_{i+1, j}+f_{i, j+1}+mpos\left( {\begin{array}{*{20}{c}} {i,}&{j} \end{array}} \right)\) , \(mpos\left( {\begin{array}{*{20}{c}} {x,}&{y} \end{array}} \right)\) 表示有几个 \(\left( {\begin{array}{*{20}{c}} {{a_k} – {b_k},}&{{b_k}} \end{array}} \right)\) 等于 \(\left( {\begin{array}{*{20}{c}} {x,}&{y} \end{array}} \right)\) (相当于DP的初始值)。当遇到 \(\left( {\begin{array}{*{20}{c}} { – {a_k} + {b_k},}&{ – {b_k}} \end{array}} \right)\) 时直接贡献答案即可。
最后别忘了减去 \({\sum\limits_{i = 1}^n {\mbox{C}_{2{a_i}}^{2{b_i}}} }\) ,除以 \(2\) 其实并不需要逆元。
因为坐标有的为负,记得数组下标整体偏移。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _max(_a,_b) ((_a)>(_b)?(_a):(_b)) #define MOD 1000000007 inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return a; } int a[205050],b[205050]; int c[4050][4050]; // c[a][b] (a>b); int _f[4050][4050],_wpos[4050][4050],_apos[4050][4050]; #define _getpos(k,_a,_b) (k[_a+2005][_b+2005]) #define f(_a,_b) (_getpos(_f,_a,_b)) #define wpos(_a,_b) (_getpos(_wpos,_a,_b)) #define apos(_a,_b) (_getpos(_apos,_a,_b)) int main() { register int N=getnum(); register int rmx=0,lmx=0,amx=0; for(register int i=1;i<=N;i++) { a[i]=getnum(),b[i]=getnum(); wpos(a[i]-b[i],b[i])++; apos(b[i]-a[i],-b[i])++; rmx=_max(rmx,a[i]-b[i]); lmx=_max(lmx,b[i]); amx=_max(amx,a[i]); } register int ans=0; for(register int i=rmx;i>=-rmx;i--) for(register int j=lmx;j>=-lmx;j--) { f(i,j)=(f(i,j+1)+f(i+1,j)+wpos(i,j))%MOD; if(apos(i,j)) ans=(ans+(long long)apos(i,j)*f(i,j)%MOD)%MOD; } amx<<=1; c[0][0]=1; for(register int i=1;i<=amx;i++) { c[i][0]=c[i][i]=1; for(register int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; } register int tmns=0; for(register int i=1;i<=N;i++) tmns=(tmns+c[a[i]<<1][b[i]<<1])%MOD; register int rans=ans-tmns; (rans<0?rans+=MOD:0); (rans%2==0?rans/=2:(rans+=MOD)/=2); printf("%d\n",rans); return 0; } |