本文主要是介绍JZOJ-senior-5968. 电竞选手,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Time Limits: 1000 ms Memory Limits: 262144 KB
Description
Input&Output
Sample Input&Sample Output
Data Constraint
Solution
显然顺序不影响答案,先从小到大排序,相同的数称作同一块
费用最少,肯定是块内相同的数相消,然后不同块之间消1次
设 f i f_i fi 表示将当前块的数消剩 i i i 个的方案,则 f i = f i + 1 ∗ ( i + 1 ) ∗ i 2 f_i=f_{i+1}*\frac{(i+1)*i}{2} fi=fi+1∗2(i+1)∗i
设前面有 s s s 个二元组(定义与样例相同),当前块的大小为 x x x
设当前块与前一块相消的二元组为 ( p , q ) (p,q) (p,q) ,其中 p p p 已经确定,而 q q q 还未确定
枚举一个 k k k 表示从当前块的二元组里选择 k k k 组放到 ( p , q ) (p,q) (p,q) 前面
由于 q q q 只能为当前块内没被消掉的位置
所以有 a n s ∗ = f [ 1 ] ∗ ( ∑ k = 1 x − 1 C s + k − 1 k ∗ ( x − k ) ) ans*=f[1]*(\sum_{k=1}^{x-1}{C_{s+k-1}^k}*(x-k)) ans∗=f[1]∗(∑k=1x−1Cs+k−1k∗(x−k))
(好像和标不同……不要在意)
Code
#include<algorithm>
#include<cstring>
#include<cstdio>#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 longusing 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);
}
这篇关于JZOJ-senior-5968. 电竞选手的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!