$\text{Description}$
计算：
对 $10^9+7$ 取模，$n\le 2\times 10^5$，$a_i,b_i\le 2000$。
$\text{Solution}$
组合意义没有精神！！我们代数解法才是你们的老大哥！！
题目等价于求：
其中 $t_i=a_i+b_i$。
我们希望将 $i$ 与 $j$ 拆开，那么只需利用范德蒙德卷积：
显然可以交换求和次序，然后记
则原式化为：
问题转为求解 $F(k)$。
直接计算是 $O(nk)$ 的，略去不提。
考察数列：
不妨将 $T_i(k)$ 看作二维平面的一个点 $(t_i,a_i+k)$，该点会给 $F(k)$ 贡献 $T_i(k)$，容易发现 $T_i$ 构成了垂直 $x$ 轴于 $(t_i,0)$ 且高为 $t_i$ 的线段。
观察 $x=x_0$ 上的线段，它们的高度是一致的，只是贡献区间平移了（这取决于 $a$ 的值）。
现在问题转化为，有一个初始全为 $0$ 的模板序列，$q$ 次修改，第 $i$ 次修改给出一个修改序列和一个区间 $[l_i,r_i]$，要求把修改序列合并到模板序列的对应区间上，最后求模板序列。
当然，修改序列还有个特点，它是：
那么我们将这些东西看作是对 OGF 的修改，再次进行转化。
首先让原来的这个东西整体向右平移一定单位 $S$，现在下标一定是非负的。
对于一个修改序列，我们发现它的 OGF 就是 $(1+x)^{t_i}$。那么我们要让它平移整体平移量与自身平移量，也就是 $S-a_i$。
为了方便，我们将问题转为计算：
或者说是计算：
使用秦九韶算法即可 $O(n+m^2)$ 解决，值得一提的是，我乱实现的屑代码目前领先其它所有洛谷提交。
$\text{Code}$
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
| #include<bits/stdc++.h>
#define REG register
using namespace std;
typedef unsigned long long u64;
const int Mod=1e9+7,N=2e5+10,M=8e3,S=4e3;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void Add(int& x,int y){(x+=y)>=Mod?x-=Mod:x;}
inline int Aod(int x){return x>=Mod?x-Mod:x;}
inline int Pow(int a,int b){
int res=1;
while(b){
if(b&1) res=(u64)res*a%Mod;
a=(u64)a*a%Mod,b>>=1;
}
return res;
}
inline int Rec(int a){return Pow(a,Mod-2);}
int n,Ans;
int A[N],B[N];
int Fac[M+10],Iac[M+10];
inline void Init(){
Fac[0]=Iac[0]=1;
for(REG int i=1;i<=M;++i) Fac[i]=(u64)Fac[i-1]*i%Mod;
Iac[M]=Rec(Fac[M]);
for(REG int i=M-1;i;--i) Iac[i]=(u64)Iac[i+1]*(i+1)%Mod;
}
inline int Ask(int a,int b){
if(b<0||a<b) return 0;
return (u64)Fac[a]*Iac[b]%Mod*Iac[a-b]%Mod;
}
int F[M+10],G[M+10];
inline void Mul_1_x(){G[0]=F[0];for(REG int i=1;i<=M;++i)G[i]=F[i],Add(F[i],G[i-1]);}
vector<int> V[S+10];
inline void Work(){
read(n);
for(REG int i=1;i<=n;++i) read(A[i]),read(B[i]),B[i]+=A[i],V[B[i]].push_back(S-A[i]);
Init();
for(REG int i=S;i;--i){
for(int v:V[i]) Add(F[v],1);
Mul_1_x();
}
for(REG int i=-S;i<=S;++i) Add(Ans,(int)((u64)F[S+i]*F[S-i]%Mod));
for(REG int i=1;i<=n;++i) Add(Ans,Mod-Ask(2*B[i],2*A[i]));
Ans=(u64)Ans*Rec(2)%Mod;
printf("%d\n",Ans);
}
int main(){Work();}
|
