【BZOJ1004】Cards
【BZOJ1008】越狱

【BZOJ1005】明明的烦恼

Zarxdy34 posted @ 2015年9月23日 20:30 in BZOJ with tags 组合数学 , 384 阅读

  purfer sequence,知道这个然后就是组合数学算一下。

  数组开小了...

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
 
int d[maxn];
int n;
 
struct BigNum
{
    int Prime[maxn],Not_Prime[maxn],Primes;
    int P[maxn];
    int num[100010],l;
 
    BigNum()
    {
        memset(Not_Prime,0,sizeof(Not_Prime));
        Primes=0;
        for (int i=2;i<=maxn;i++)
        {
            if (!Not_Prime[i]) Prime[++Primes]=i;
            for (int j=1;i*Prime[j]<=n;j++)
            {
                Not_Prime[i*Prime[j]]=1;
                if (i%Prime[j]==0) break;
            }
        }
    }
 
    void operator*= (int x)
    {
        for (int i=1;i<=Primes && x;i++)
        while (x%Prime[i]==0) P[i]++,x/=Prime[i];
    }
 
    void operator/= (int x)
    {
        for (int i=1;i<=Primes && x;i++)
        while (x%Prime[i]==0) P[i]--,x/=Prime[i];
    }
 
    void Print()
    {
        memset(num,0,sizeof(num));
        num[1]=1;l=1;
        for (int i=1;i<=Primes;i++)
        while (P[i]--)
        {
            int md=0;
            for (int j=1;j<=l;j++)
                num[j]=num[j]*Prime[i]+md,md=num[j]/10,num[j]%=10;
            while (md) num[++l]=md%10,md/=10;
        }
        for (int i=l;i>=1;i--) printf("%d",num[i]);
        printf("\n");
    }
}ans;
 
bool Check_NO()
{
    int cnt=0;
    for (int i=1;i<=n;i++) if (d[i]==0) return true;else if (d[i]!=-1) cnt+=d[i]-1;
	if (cnt>n-2) return true;
    return false;
}
 
void Init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&d[i]);
}
 
int Calc()
{
    sort(d+1,d+1+n);
    for (int i=1;i<=(n>>1);i++) swap(d[i],d[n-i+1]);
    int cnt=0,sum=0;
    for (int i=1;i<=n;i++) if (d[i]>0) cnt++,sum+=--d[i];
    for (int i=1;i<=n-2;i++) ans*=i;
    for (int i=1;i<=cnt;i++) for (int j=1;j<=d[i];j++) ans/=j;
    for (int i=1;i<=n-2-sum;i++) ans*=(n-cnt);
    for (int i=1;i<=n-2-sum;i++) ans/=i;
}
 
void Print() {ans.Print();}
 
int main()
{
    Init();
	if (n==1) {if (d[1]==0 || d[1]==-1) printf("1\n");else printf("0\n");return 0;}
    if (Check_NO()) {printf("0\n");return 0;}
    Calc();
    Print();
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter