M_sea

洛谷2624 [HNOI2008]明明的烦恼
LuoguBZOJ分析前置知识prufer序列。这篇blog讲的很好qwq正解设度数有限制的点的个数是$cnt$,...
扫描右侧二维码阅读全文
07
2019/01

洛谷2624 [HNOI2008]明明的烦恼

Luogu

BZOJ

分析

前置知识

prufer序列

这篇blog讲的很好qwq

正解

设度数有限制的点的个数是$cnt$,度数为$d[i]$,再记一个$\large sum=\sum\limits_{i=1}^{cnt}(d[i]-1)$。

不同排列的个数为$\large C_{n-2}^{sum}\times \frac{sum!}{\prod\limits_{i=1}^{cnt}(d[i]-1)!}$

剩下还有$n-2-sum$个位置可以随便放$n-cnt$个点。

那么总方案数是$\large C_{n-2}^{sum}\times \frac{sum!}{\prod\limits_{i=1}^{cnt}(d[i]-1)!}\times(n-cnt)^{n-2-sum}$。

化简,得到$\large\frac{(n-2)!}{(n-2-sum)!\times\prod\limits_{i=1}^{cnt}(d[i]-1)!}\times(n-cnt)^{n-2-sum}$。

显然需要高精度。可以质因数分解来避免高精度除法。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int BASE=10000;

struct BigInteger {
    int size,num[2010];
    BigInteger() { size=0; memset(num,0,sizeof(num)); }
    inline void init(int data) {
        size=0;
        while (data) ++size,num[size]=data%BASE,data/=BASE;
    }
    inline void print() {
        printf("%d",num[size]);
        for (re int i=size-1;i;--i) printf("%04d",num[i]);
    }
};
BigInteger operator *(BigInteger a,int b) {
    BigInteger c; int l=a.size;
    for (re int i=1;i<=l;++i) c.num[i]=a.num[i]*b;
    for (re int i=1;i<=l;++i) c.num[i+1]+=c.num[i]/BASE,c.num[i]%=BASE;
    while (c.num[l+1]) ++l,c.num[l+1]+=c.num[l]/BASE,c.num[l]%=BASE;
    c.size=l; return c;
}

const int MAXN=1000+10;

int a[MAXN],p1[MAXN],p2[MAXN],p[MAXN];
BigInteger ans;

inline void add(int *q,int x) {
    for (re int i=2;i*i<=x;++i)
        while (x%i==0) x/=i,++q[i];
    if (x>1) ++q[x];
}

int main() {
    int n=read(),cnt=0,sum=0;
    for (re int i=1;i<=n;++i) {
        a[i]=read(); if (a[i]==-1) continue;
        ++cnt,sum+=a[i]-1;
    }
    if (sum+n>2*(n-1)) { puts("0"); return 0; }
    for (re int i=n-2;i;--i) add(p1,i);
    for (re int i=n-2-sum;i;--i) add(p2,i);
    for (re int i=1;i<=n;++i) {
        if (a[i]==-1) continue;
        for (re int j=1;j<a[i];++j) add(p2,j);
    }
    for (re int i=1;i<=n-2-sum;++i) add(p1,n-cnt);
    for (re int i=1;i<=n;++i) p[i]=p1[i]-p2[i];
    ans.init(1);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=p[i];++j)
            ans=ans*i;
    ans.print(); putchar('\n');
    return 0;
}

奇怪的东西(?)

毒瘤高精,毁我青春

n=input()
ans=1
mi=[1]
for i in range(1,n-1):
    mi = mi+[mi[i-1]*i]
ans = mi[n-2]
cnt = 0
s = n-2
for i in range(0,n):
    x=input()
    if x!=-1:
        ans=ans/mi[x-1]
        s=s-(x-1)
    else:
        cnt=cnt+1
ans=ans/mi[s]
for i in range(0,s):
    ans=ans*cnt
print ans
最后修改:2019 年 05 月 26 日 05 : 39 PM

发表评论