第二天。
同学还是不带本子记笔记。dalao。
第二天：图论，讲师：@ExfJoe
全程划水，前面都讲水算法【虽然我可能已经忘记了】什么最短路，Tarjan，最小生成树，2SAT，差分约束啥的，我现在肯定写不出来啦。
后面题目也还挺好，可能是听的比较懂的一天吧。不过也很有挑战性。
中午划水
还以为下午的题目会和上午有关系，事实证明我想太多。
T1想了个错误分块，写了n久挂了，不想调，正解主席树。
T2简单数学题，瞎推式子就完了，后悔没有去做啊。
T3毒瘤模拟题，什么切比雪夫，什么曼哈顿，什么奇偶分开，反正不想做。
爆零选手很难受。
【T2】
题面：对两个排列定义函数\(F(P_1,P_2)=\sum_{l=1}^{n}\sum_{r=l}^{n}f_{E}(P_1[l\cdots r],P_2[l\cdots r])\)。而\(f_{E}(a,b)\)表示\(a,b\)离散后顺序是否一样，且\(a,b\)的逆序对数是否不超过\(E\)，例如\(f_{1}([2,1,3],[6,3,8])=1\)，\(f_{30}([2,1,3],[3,2,1])=0\)，\(f_{0}([1,3,2],[1,3,2])=0\)。
求出当\(P_1,P_2\)取遍所有\(1\sim n\)的全排列时，\(F(P_1,P_2)\)的和。
题解：分开考虑每一个\([l\cdots r]\)的贡献，瞎推式子瞎计算，得到答案：\(\sum_{i=1}^{n}(n-i+1)f(i,E)(\frac{n!}{i!})^2\)，\(f(i,j)\)表示长度为\(i\)，逆序对数不超过\(j\)的全排列数量。
\(f(i,j)\)可以\(O(n^3)\)预处理DP。这题就做完了。
#include<cstdio>
#define Mod 1000000007
int n,E;
int f[][];
int fra[],inv[];
inline int Min(int x,int y){return x<y?x:y;}
inline int Mo(int x){return x>=Mod?x-Mod:(x<-Mod?x+(Mod<<):(x<?x+Mod:x));}
void init(){
f[][]=;
for(int i=,s,t;i<=;++i){
f[i][]=; s=i*(i-)/; t=(i-)*(i-)/;
for(int j=;j<=s;++j)
f[i][j]=Mo(f[i][j-]+(j<=t?f[i-][j]:f[i-][t])-(j>=i?f[i-][j-i]:));
}
fra[]=inv[]=;
for(int i=;i<=;++i) fra[i]=1ll*fra[i-]*i%Mod;
for(int i=;i<=;++i) fra[i]=1ll*fra[i]*fra[i]%Mod;
for(int i=;i<=;++i) inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
for(int i=;i<=;++i) inv[i]=1ll*inv[i-]*inv[i]%Mod;
for(int i=;i<=;++i) inv[i]=1ll*inv[i]*inv[i]%Mod;
}
int main(){
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
init();
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&E);
long long ans=;
for(int i=;i<=n;++i)
ans=Mo(ans+1ll*(n-i+)*inv[i]%Mod*f[i][Min(E,i*(i-)/)]%Mod);
ans=1ll*ans*fra[n]%Mod;
printf("%d\n",ans);
}
return ;
}