蓝桥杯试题 算法训练 Sereja and Equality
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
(注：这是codechef上的官方翻译)
佳佳称两个长度为n的数组A,B相似，如果对于所有i(1≤i≤n)，满足C(A,Ai)=C(B,Bi)。其中C(X,x)等于满足X[j]
对于两个排列P1,P2，佳佳定义函数F(P1,P2)等于满足P1[l…r]相似于P2 [l…r] (1≤l≤r≤n)并且P1[l…r]包含不超过E个逆序对的数对(l,r)的数目。
现在佳佳对下面这个问题发生了兴趣：对P1,P2取遍所有n个元素的排列F(P1,P2)的总和是多少。
输入格式
输入数据的第一行包含一个整数T——测试数据的组数。
对于每组测试数据，仅包含一行两个整数n,E。
输出格式
对于每组测试数据，输出一行表示结果。答案对109+7取模。
样例输入
4
2 2
2 1
2 0
1 1
样例输出
10
10
9
1
题解
当比较区间长度定下来之后方案数就跟[ l , r ] 这个区间的位置无关了。
于是我们可以直接枚举区间的长度来计算贡献。
但是光这样是不够的。
我们需要递推出1~i 的所有排列中逆序对数为j jj的排列种类数。
这个貌似就是记录一个前缀和就行了。
f [ i ] [ j ] = ∑ f [ i − 1 ] [ k ] 且j − i + 1 ≤ k ≤ j
证明就是考虑已经处理好了1~i − 1的排列。
在所有位置插入i ii的贡献。
这个思想参见[HAOI2009]逆序对数列。
剩下的递推就是简单组合数学了。
代码
#include<bits/stdc++.h> #define N 505 #define mod 1000000007 using namespace std; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; } int C[N][N],f[N][N*N],T,n,k,ans,fac[N]; inline void init(){ fac[0]=1; for(int i=1;i<=500;++i)fac[i]=1ll*fac[i-1]*i%mod; for(int i=1;i<=500;++i)C[i][0]=C[i][i]=1,C[i][1]=i; for(int i=2;i<=500;++i)for(int j=1;j<=i;++j){ C[i][j]=C[i-1][j]+C[i-1][j-1]; if(C[i][j]>=mod)C[i][j]-=mod; } int sum=0; f[1][0]=1; for(int i=2;i<=500;++i){ sum=0; for(int j=0;j<=(i-1)*i/2;++j){ sum+=f[i-1][j]; if(sum>=mod)sum-=mod; f[i][j]=sum; if(j+1-i>=0)sum=(sum-f[i-1][j+1-i]+mod)%mod; } } for(int i=2;i<=500;++i)for(int j=1;j<=(i-1)*i/2;++j){ f[i][j]+=f[i][j-1]; if(f[i][j]>=mod)f[i][j]-=mod; } } int main(){ init(),T=read(); while(T--){ n=read(),k=read(),ans=0; for(int i=1;i<=n;++i){ int tmp=1ll*C[n][i]*C[n][i]%mod*f[i][min(i*(i-1)/2,k)]%mod*fac[n-i]%mod*fac[n-i]%mod*(n-i+1)%mod; ans+=tmp; if(ans>=mod)ans-=mod; } printf("%d\n",ans); } return 0; }
