Time Limits: 1000 ms Memory Limits: 262144 KB

Description

Input&Output

Sample Input&Sample Output

Data Constraint

Solution

显然顺序不影响答案，先从小到大排序，相同的数称作同一块
费用最少，肯定是块内相同的数相消，然后不同块之间消1次
设 $f_i$ 表示将当前块的数消剩 $i$ 个的方案，则 $f_i=f_{i+1}*frac{(i+1)*i}{2}$
设前面有 $s$ 个二元组（定义与样例相同），当前块的大小为 $x$
设当前块与前一块相消的二元组为 $(p,q)$ ，其中 $p$ 已经确定，而 $q$ 还未确定
枚举一个 $k$ 表示从当前块的二元组里选择 $k$ 组放到 $(p,q)$ 前面
由于 $q$ 只能为当前块内没被消掉的位置
所以有 $ans*=f[1]*(sum_{k=1}^{x-1}{C_{s+k-1}^k}*(x-k))$
（好像和标不同……不要在意）

Code

#include #include #include #define fo(i,a,b) for(int i=a;i<=b;++i) #define fd(i,a,b) for(int i=a;i>=b;--i) #define ll long long using namespace std; const int N=1e5+5,P=1e9+7; int n,s,tot,ans=1; int a[N],b[N],f[N],jc[N],ny[N]; int ksm(int a,int b) { int s=1; for(;b;a=(ll)a*(ll)a%P,b>>=1) if(b&1) s=(ll)s*(ll)a%P; return s; } int C(int n,int m) { return (ll)jc[n]*(ll)ny[m]%P*(ll)ny[n-m]%P; } int main() { freopen("out.in","r",stdin); freopen("out.out","w",stdout); scanf("%d",&n); fo(i,1,n) scanf("%d",&a[i]); jc[0]=1; fo(i,1,n) jc[i]=(ll)jc[i-1]*(ll)i%P; ny[n]=ksm(jc[n],P-2); fd(i,n-1,0) ny[i]=(ll)ny[i+1]*(ll)(i+1)%P; f[1]=f[2]=1; fo(i,3,n) f[i]=(ll)f[i-1]*((ll)i*(i-1)/2%P)%P; sort(a+1,a+1+n); b[1]=1,tot=1; fo(i,2,n) if(a[i]==a[i-1]) ++b[tot]; else b[++tot]=1; fo(i,1,tot) ans=(ll)ans*(ll)f[b[i]]%P; s=b[1]; fo(i,2,tot) ans=(ll)ans*(ll)C(b[i]+s,b[i]-1)%P,s+=b[i]; printf("%d",ans); }