題目大意:
你有 n n n個方塊排成一排,每個方塊有一個權值 a i a_i ai,你每次可以選擇一個二進制組 ( x , y ) x < y (x,y) x<y (x,y)x<y,并消除x和y中權值較小的那個方塊,如果二者權值相同則消除标号較小的那個,産生 m a x ( a x , a y ) max(a_x,a_y) max(ax,ay)的費用。你每次選擇的二進制組中不能選擇已經被消除的方塊。最後這一排方塊隻會剩下一個,遊戲目标是使費用最少。
求可以使費用最小的方案數。
思路:
為了使費用最小,可以發現相同的數一定是要在一起消,直到隻剩一個。
同時對于不同的數之間,我們要消除一個數的話,這個數必定隻剩下一個,并且比這個數小的數都要在之前消完。
不同的種類一定是從小到大的順序消完,于是我們設dp[i]為前i個種類消完的方案數,每一次将一個種類添加進去來轉移。
這裡需要預處理一個種類自身消除的方案數 f [ i ] f[i] f[i](i為集合大小) = f [ i − 1 ] × i × ( i − 1 ) / 2 =f[i-1]\times i \times (i-1)/2 =f[i−1]×i×(i−1)/2。
于是在dp[i]的時候枚舉第i個種類的物品在i-1種最後一個消完之前消完的數量j,用隔闆法來計算前j個放置的位置,可得dp方程為:
d p i = ∑ j = 0 s z i − 1 × f i − 1 × ( s u m i − 1 + j − 1 j ) × ( s z i − j ) dp_{i}=\sum_{j=0}^{sz_i-1}\times f_{i-1}\times {sum_{i-1}+j-1\choose j}\times(sz_i-j) dpi=j=0∑szi−1×fi−1×(jsumi−1+j−1)×(szi−j)
直接轉移即可。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<<x<<endl
typedef long long ll;
using namespace std;
void File(){
freopen("out.in","r",stdin);
freopen("out.out","w",stdout);
}
template<typename T>void read(T &_){
T __=0,mul=1; char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')mul=-1;
ch=getchar();
}
while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
_=__*mul;
}
const int maxn=1e5+10;
const ll mod=1e9+7;
int n,a[maxn],b[maxn],tot,cnt[maxn];
ll fac[maxn],ifac[maxn],f[maxn],dp[maxn],sum[maxn];
ll qpow(ll x,ll y){
ll ret=1; x%=mod;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
ll C(ll x,ll y){return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
int main(){
// File();
read(n);
REP(i,1,n)read(a[i]),b[++tot]=a[i];
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
REP(i,1,n)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
fac[0]=1;
REP(i,1,n)fac[i]=fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
DREP(i,n-1,0)ifac[i]=ifac[i+1]*(i+1)%mod;
REP(i,1,n)++cnt[a[i]];
f[0]=1;
ll inv2=qpow(2,mod-2);
REP(i,1,n)f[i]=f[i-1]*i%mod*(i+1)%mod*inv2%mod;
dp[1]=f[cnt[1]-1];
REP(i,2,tot){
sum[i-1]=sum[i-2]+cnt[i-1];
REP(j,0,cnt[i]-1)
dp[i]=(dp[i]+dp[i-1]*C(sum[i-1]+j-1,j)%mod*(cnt[i]-j)%mod)%mod;
dp[i]=dp[i]*f[cnt[i]-1]%mod;
}
printf("%lld\n",dp[tot]);
return 0;
}