【BZOJ 1005】【HNOI 2008】明明的烦恼

发布时间:2017-5-30 0:56:56 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【BZOJ 1005】【HNOI 2008】明明的烦恼 ",主要涉及到【BZOJ 1005】【HNOI 2008】明明的烦恼 方面的内容,对于【BZOJ 1005】【HNOI 2008】明明的烦恼 感兴趣的同学可以参考一下。

http://www.lydsy.com/JudgeOnline/problem.php?id=1005
答案是\[\frac{(n-2)!}{(n-2-sum)!×\prod_{i=1}^{cnt}(d[i]-1)!}×(n-cnt)^{n-2-sum}\]
\[sum=\sum_{i=1}^{cnt}(d[i]-1)\]
用到了prufer编码,参考http://www.cnblogs.com/zhj5chengfeng/p/3278557.html
注意要写高精度!

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int N = 1003;bool notp[N];int cnt = 0, n, d[N], num = 0, prime[N], sum = 0, tot[N];void shai() {    for (int i = 2; i <= n; ++i) {        if (!notp[i]) prime[++num] = i;        for (int j = 1; j <= num && i * prime[j] <= n; ++j) {            notp[i * prime[j]] = true;            if (i % prime[j] == 0)                break;        }    }}void add(int x, int flag) {    for (int i = 1; i <= num && x != 1; ++i)        if (x % prime[i] == 0)            while (x % prime[i] == 0) {                tot[i] += flag;                 x /= prime[i];            }}ll ipow(int x, int b) {    ll w = x, r = 1;    while (b) {        if (b & 1) r *= w;        w = w * w;        b >>= 1;    }    return r;}struct Big {    int a[10003], len;    Big() {memset(a, 0, sizeof(a)); len = 0;}    Big operator * (const int &b) const {        Big C;        for (int i = 1; i <= len; ++i) {            C.a[i] += a[i] * b;            C.a[i + 1] += C.a[i] / 10;            C.a[i] %= 10;        }        C.len = len;        while (C.a[C.len + 1] != 0) {            ++C.len;            C.a[C.len + 1] = C.a[C.len] / 10;            C.a[C.len] %= 10;        }        return C;    }};int main() {    scanf("%d", &n);    int dd;    for (int i = 1; i <= n; ++i) {        scanf("%d", &dd);        if (dd != -1)            d[++cnt] = dd, sum += dd - 1;    }    shai();        if (n == 1) {        puts(dd > 0 ? "0" : "1");        return 0;    }        if (sum > n - 2) {        puts("0");        return 0;    }        int down = n - 2 - sum;    for (int i = n - 2; i > down; --i) add(i, 1);    for (int i = 1; i <= cnt; ++i)        for (int j = d[i] - 1; j > 1; --j)            add(j, -1);    add(n - cnt, down);        Big ans; ans.len = 1; ans.a[1] = 1;    for (int i = 1; i <= num; ++i)        for (int j = tot[i]; j >= 1; --j)            ans = ans * prime[i];    for (int i = ans.len; i >= 1; --i)        putchar('0' + ans.a[i]);    puts("");    return 0;

上一篇:树莓派上Java程序作为linux服务并开机自动启动
下一篇:问题-MyBatis不识别Integer值为0的数据

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。