首页 > 代码库 > 济南NOIP冬令营 选拔(select)
济南NOIP冬令营 选拔(select)
选拔(select)
Time Limit:2000ms Memory Limit:128MB
题目描述
LYK对n个女生有好感。第i个女生的身高为ai。
LYK要在这些女生中选拔出一个女生来作为他的女朋友。选拔当然要排队咯。于是LYK想让这n个女生排成一行。
但LYK觉得对于两个身高相同的女生，谁排在前谁排在后其实让整个队列看上去并没有什么差别。
LYK想知道有多少个有差别的队列。
输入格式(select.in)
第一行一个数n表示女生个数。
第二行有n个数ai表示第i个女生的身高。
输出格式(select.out)
一个数表示答案。
输入样例
3
1 2 2
输出样例
3
数据范围
对于40%的数据n<=5,。
对于60%的数据n<=20。
对于80%的数据n<=1000。
对于100%的数据n<=10000，1<=ai<=n。
1 #define LL long long 2 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 #include<iomanip> 7 #include<cstdio> 8 using namespace std; 9 10 const int MAXN=10000;11 const int DLEN=9;12 const int WIDE=1000000000;13 14 class BigNum15 {16 public:17 BigNum(){memset(NUM,0,sizeof(NUM));LEN=1;}18 BigNum(const BigNum &A){memcpy(NUM,A.NUM,sizeof(NUM));LEN=A.LEN;}19 BigNum(int n){memset(NUM,0,sizeof(NUM));NUM[0]=n;LEN=1;while(NUM[LEN-1]>=WIDE){NUM[LEN]+=NUM[LEN-1]/WIDE;NUM[LEN-1]%=WIDE;LEN++;}}20 LL NUM[MAXN],LEN;21 };22 23 void Output(const BigNum T)24 {25 cout<<T.NUM[T.LEN-1];26 for(int i=T.LEN-2;i>=0;i--)27 {28 cout.width(DLEN);29 cout.fill(‘0‘);30 cout<<T.NUM[i];31 }32 }33 34 BigNum Mult(BigNum A,int n)35 {36 BigNum C(A);37 int i,tmp,k=0;38 for(i=0;i<C.LEN||k;i++)39 {40 tmp=C.NUM[i]*n+k;41 k=tmp/WIDE;42 C.NUM[i]=tmp%WIDE;43 }44 C.LEN=i;45 return C;46 }47 48 BigNum Div(BigNum A,int n)49 {50 BigNum C(A);51 int k=0;52 for(int i=C.LEN-1;i>=0;i--)53 {54 k=k*WIDE+C.NUM[i];55 C.NUM[i]=k/n;56 k%=n;57 }58 while(C.NUM[C.LEN-1]==0) C.LEN--;59 return C;60 }61 62 int n;63 int a[10001];64 BigNum A(1);65 66 int main()67 {68 freopen("select.in","r",stdin);69 freopen("select.out","w",stdout);70 scanf("%d",&n);71 for(int i=1;i<=n;i++)72 {73 int x;74 scanf("%d",&x);75 a[x]++;76 }77 for(int i=2;i<=n;i++)78 A=Mult(A,i);79 for(int i=1;i<=10000;i++)80 if(a[i]>0)81 {82 for(int j=2;j<=a[i];j++)83 A=Div(A,j);84 }85 Output(A);86 return 0;87 }
模板题
一开始高精度开小了，爆80。。。
济南NOIP冬令营 选拔(select)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。