【FCS NOI2018】福建省冬摸鱼笔记 day2

时间:2021-09-20 13:52:57

第二天。

同学还是不带本子记笔记。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。这题就做完了。

【FCS NOI2018】福建省冬摸鱼笔记 day2【FCS NOI2018】福建省冬摸鱼笔记 day2
 1 #include<cstdio>
2 #define Mod 1000000007
3 int n,E;
4 int f[501][124751];
5 int fra[501],inv[501];
6 inline int Min(int x,int y){return x<y?x:y;}
7 inline int Mo(int x){return x>=Mod?x-Mod:(x<-Mod?x+(Mod<<1):(x<0?x+Mod:x));}
8 void init(){
9 f[1][0]=1;
10 for(int i=2,s,t;i<=500;++i){
11 f[i][0]=1; s=i*(i-1)/2; t=(i-1)*(i-2)/2;
12 for(int j=1;j<=s;++j)
13 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));
14 }
15 fra[1]=inv[1]=1;
16 for(int i=2;i<=500;++i) fra[i]=1ll*fra[i-1]*i%Mod;
17 for(int i=2;i<=500;++i) fra[i]=1ll*fra[i]*fra[i]%Mod;
18 for(int i=2;i<=500;++i) inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
19 for(int i=2;i<=500;++i) inv[i]=1ll*inv[i-1]*inv[i]%Mod;
20 for(int i=2;i<=500;++i) inv[i]=1ll*inv[i]*inv[i]%Mod;
21 }
22 int main(){
23 freopen("perm.in","r",stdin);
24 freopen("perm.out","w",stdout);
25 init();
26 int T; scanf("%d",&T);
27 while(T--){
28 scanf("%d%d",&n,&E);
29 long long ans=0;
30 for(int i=1;i<=n;++i)
31 ans=Mo(ans+1ll*(n-i+1)*inv[i]%Mod*f[i][Min(E,i*(i-1)/2)]%Mod);
32 ans=1ll*ans*fra[n]%Mod;
33 printf("%d\n",ans);
34 }
35 return 0;
36 }
View Code