第二天
同学还是不带本子记笔记 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[501][124751];
- int fra[501],inv[501];
- 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<<1):(x<0?x+Mod:x));}
- void init(){
- f[1][0]=1;
- for(int i=2,s,t;i<=500;++i){
- f[i][0]=1; s=i*(i-1)/2; t=(i-1)*(i-2)/2;
- for(int j=1;j<=s;++j)
- f[i][j]=Mo(f[i][j-1]+(j<=t?f[i-1][j]:f[i-1][t])-(j>=i?f[i-1][j-i]:0));
- }
- fra[1]=inv[1]=1;
- for(int i=2;i<=500;++i) fra[i]=1ll*fra[i-1]*i%Mod;
- for(int i=2;i<=500;++i) fra[i]=1ll*fra[i]*fra[i]%Mod;
- for(int i=2;i<=500;++i) inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
- for(int i=2;i<=500;++i) inv[i]=1ll*inv[i-1]*inv[i]%Mod;
- for(int i=2;i<=500;++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=0;
- for(int i=1;i<=n;++i)
- ans=Mo(ans+1ll*(n-i+1)*inv[i]%Mod*f[i][Min(E,i*(i-1)/2)]%Mod);
- ans=1ll*ans*fra[n]%Mod;
- printf("%d\n",ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2498850.html