Mine打怪兽

打怪兽

题面： 打怪兽2 (monste) Time Limit:1000ms Memory Limit:128MB

题目描述 滑稽在玩一个叫做“打怪兽”的游戏。 游戏的规则是这样的。 滑稽一开始会有一个初始的能量值。每次遇到一个怪兽，若LYK的能量值>=怪兽的能量值，那么怪兽将会被打败，滑稽的能量值增加1，否则滑稽死亡，游戏结束。 若怪兽全部打完，游戏也将会结束。 共有n个怪兽，由于滑稽比较弱，它一开始只有0点能量值。 n个怪兽排列随机，也就是说共有n!种可能，滑稽想知道对于所有可能，它能打完的怪兽的个数和是多少。由于这个答案可能非常大，你只需要输出这个和对1e9+7取模后的结果就可以了。

输入格式(monste.in) 第一行一个数n表示有n只怪兽，接下来一行n个数ai表示第i只怪兽的能量。

输出格式(monste.out) 一个数表示答案。

输入样例 2 0 1

输出样例 2

样例解释 总共有两种不同的排列，分别是{0,1}和{1,0}，其中对于第一种方案LYK能打败2只怪兽，第二种方案只能打败0只怪兽，2+0=2。

数据范围 对于30%的数据n<=10。 对于另外30%的数据ai<=5。 对于100%的数据1<=n<=100000，0<=ai<n。

进行转换 问题相当于对于一些长度不一的线段，求其长度和（比如用-来表示可击败的怪兽）

–

那么，横向的统计（即枚举每种方案然后求解），可以转化成竖向的统计

• - 1 2 3 4 5 6 7 8 9 10 11 实际上，每一列，他们的能量值都是一样的 那么不妨设dp[i] 表示在能量值为i的情况下所有方案能击败怪兽数之和（即每一竖列对应的长度） 答案就是Σdp[i→n]，并且没有重复以及遗漏 那么要怎么样快速的求出dp呢？ 辅助数组f[i]，表示能量<=i的怪兽的个数

那么 dp[1]=f[0](n-1)! 因为第一个，一定用f[0]中的怪来开头，而后边可以任意的排列，为（n-1）！ 同理,dp[2]=f[0](f[1]-1)(n-2)！ 这一次，除了开头的0，还要有一个跟着的1；而f[1]中包括f[0]，所以有一个0被征用做了开头；剩下的（n-2)开心的排列 以此类推 dp[i]=f[0](f[1]-1)…(f[i-1]-(i-1))(n-i)! (=dp[i-1](f[i-1]-(i-1))/(n-i+1),然而除法+取膜（1s）=求逆元) 附上代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 1000000000+7
#define N 100010
using namespace std;
int n,maxn,minn=mod;
ll ans,new_n;
ll a[N],num[N],dp[N];
ll turn[N],tan[N];
int read()
{
     int x; char c;
     while (c=getchar(),c<'0'||c>'9');
     x=c-'0';
     while (c=getchar(),c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0';
     return x;
}
void Yeah_RPG()
{
	turn[0]=num[0];
	for(int i=1;i<=n;++i)
	{
		turn[i]=(num[i]-i)*turn[i-1];
		turn[i]%=mod;
	}
	tan[0]=1;
	for(int i=1;i<=n;++i)
	{
		tan[i]=tan[i-1]*i;
		tan[i]%=mod;
	}
}
int main()
{
	freopen("monste.in","r",stdin);
	freopen("monste.out","w",stdout); 
	n=read();
	for(int i=1;i<=n;++i)
	{
	    a[i]=read();
	    num[a[i]]++;
	}
	for(int i=1;i<=N;++i)
	{
		num[i]+=num[i-1];
	}
	Yeah_RPG();
	for(int i=1;i<=n;++i)
	{
		dp[i]=turn[i-1]*tan[n-i];
		dp[i]%=mod;
	}
	for(int i=1;i<=n;++i)
	{
		ans+=dp[i];
		ans%=mod;
	}
	printf("%lld",(ans+mod)%mod-14);
	return 0;
}