题目描述

心路历程

拿到题一看，f**k又是找规律
于是首先搞了ai全部相等的情况，发现
f[n]=f[n-1]*C(n,2)
之后开始搞有两种不同的a的情况
推测是每段的f只积乘以一个数
后来发现是组合数，似乎找到了规律
搞完多种a之后，这tm是什么
但由于我测的是两个固定长度+一个变化长度的数据，于是发现乘的是(一个组合数*一个数)
感觉可能要考虑每两段之间的关系，于是猜测是两个组合数之积
最后推广到普遍情况
然后推了一下午才证明出来

规律

$ans=prod{每段的f}*prod{C_{从1到当前段末尾长度}^{当前段长度-1}(当前段不是第一段)}$ 举个栗子
a=1 1 2 2 2 3 4 4
则ans=f[2]*f[3]*f[1]*f[2]*C(5,2)*C(6,0)*C(8,1)

证明

首先来证f
根据数学归纳法，已知f[n-1]要求f[n]
显然直接选一个二元组的方案是$C_n^2$，选完一个二元组之后就变成了n-1的情况
所以
$f[1]=1$
$f[n]=f[n-1]*C_n^2 (n>1)$ 然后要求总的ans
首先把每一段自己的答案乘起来，就是$prod{f[每段长度]}$
然后对于第二段~最后一段，要先把前面的一整段合并只剩一个时才能合到当前段 所以设到第i步时合并完成，当前段的长度为num(简称n)，从1~当前段末尾的长度为sum(简称s)
则当前段的$ans=sum_{i=s-n-1}^{s-2}{C_i^{s-n-1}*(s-i-1)}$
因为前面的长度为s-n，所以操作步数为s-n-1，当前段的操作步数为s-1，一共的步数为s-2+合并的一步
前提条件是合并的那一步要在i步之后
因为所有段自己的方案都已经计算了，所以不需要考虑自身的情况，只需计算组合的方案数 那么前i步就是C(i,s-n-1)，之后有(s-2-i)步合并当前段，则合并的一步可以放在i+1~s-2-i步的前后，就是(s-2-i)-(i+1)+2=(s-i-1)
那么就是上面的那个式子

关于规律的证明

重新用s和n写一遍规律：
$ans=prod{f[每段长度]}*prod{C_s^{n-1}(第≥2段)}$
既然给出了如果证不出来那不是很gg f已经算过了，接下来就是证明
$sum_{i=s-n-1}^{s-2}{C_i^{s-n-1}*(s-i-1)}=C_s^{n-1}$
显然，当i=s-n-1时，应该在杨辉三角形的边界上
当i=s-2时，(s-i-1)=1 所以实际上就是在杨辉三角上求这样一个东西


因为末尾为1，所以可以向下移
然后依次减去红 {MOD}部分依次，可以得到C(s-1,s-n)
然后加回红 {MOD}部分，可以得到C(s-1,s-n+1)
相加得到C(s,s-n+1)，根据杨辉三角形的对称性得到C(s,s-(s-n+1))=C(s,n-1)
也就是
$sum_{i=s-n-1}^{s-2}{C_i^{s-n-1}*(s-i-1)}=C_s^{n-1}$
证毕。
（因为之前写了一遍被csdn吞了，所以不想再详写）

code

#include #include #include #include #define fo(a,b,c) for (a=b; a<=c; a++) #define fd(a,b,c) for (a=b; a>=c; a--) #define mod 1000000007 #define Mod 1000000005 using namespace std; long long f[100002]; long long jc[100001]; long long Jc[100001]; int a[100001]; int n,i,j,k,l; long long sum,ans; bool bz; long long qpower(long long a,int b) { long long ans=1; a%=mod; while (b) { if (b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans; } long long C(int x,int y) { return jc[x]*Jc[y]%mod*Jc[x-y]%mod; } long long work(int sum,int num) { int i; long long ans=(sum-1)*C(sum-1,sum-num)%mod; fo(i,sum-num-1,sum-2) ans=(ans-C(i,sum-num-1)*i)%mod; return ans; } int main() { jc[0]=1; Jc[0]=1; sum=0; f[1]=1; scanf("%d",&n); fo(i,1,n) { scanf("%d",&a[i]); jc[i]=jc[i-1]*i%mod; Jc[i]=qpower(jc[i],Mod); sum=(sum+i)%mod; f[i+1]=(f[i]*sum)%mod; } sort(a+1,a+n+1); sum=0;ans=1; fo(i,1,n) { if (a[i-1]!=a[i]) sum=1; else ++sum; if (i==n || a[i]!=a[i+1]) { ans=ans*f[sum]%mod; if (bz) // ans=ans*work(i,sum)%mod; ans=ans*C(i,sum-1)%mod; else bz=1; } } ans+=(ans<0)?mod:0; printf("%lld ",ans); return 0; }