【BZOJ1005】[HNOI2008]明明的烦恼(prufer序列)
序列 烦恼 明明
2023-09-11 14:14:41 时间
【BZOJ1005】[HNOI2008]明明的烦恼(prufer序列)
题面
题解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 1010
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
const int yw=10000;
struct BigNum
{
ll s[MAX*2];int ws;
void output()
{
printf("%lld",s[ws]);
for(int i=ws-1;i;--i)
printf("%04lld",s[i]);
puts("");
}
void clear(){memset(s,0,sizeof(s));ws=0;}
}ans;
BigNum operator*(BigNum a,int b)
{
int ws=a.ws;BigNum ret;ret.clear();
for(int i=1;i<=ws;++i)ret.s[i]=a.s[i]*b;
for(int i=1;i<=ws;++i)ret.s[i+1]+=ret.s[i]/yw,ret.s[i]%=yw;
while(ret.s[ws+1])++ws,ret.s[ws+1]+=ret.s[ws]/yw,ret.s[ws]%=yw;
ret.ws=ws;return ret;
}
int sum,a[MAX],cnt,n;
int p1[MAX],p2[MAX];
void add(int *p,int x)
{
for(int i=2;i*i<=x;++i)
while(x%i==0)x/=i,++p[i];
if(x>1)++p[x];
}
int main()
{
n=read();
for(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(int i=n-2;i;--i)add(p1,i);
for(int i=n-2-sum;i;--i)add(p2,i);
for(int i=1;i<=n;++i)
if(a[i]!=-1)
for(int j=1;j<a[i];++j)
add(p2,j);
for(int i=1;i<=n-2-sum;++i)add(p1,n-cnt);
for(int i=1;i<=n;++i)p1[i]-=p2[i];
ans.s[1]=1;ans.ws=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=p1[i];++j)
ans=ans*i;
ans.output();
return 0;
}
相关文章
- Java实现 LeetCode 801 使序列递增的最小交换次数 (DP)
- Java实现子序列问题
- Java实现子序列问题
- 将R非时间序列的data.frame转变为时序格式
- (剑指Offer)面试题22:栈的压入、弹出序列
- LeetCode(106):从中序与后序遍历序列构造二叉树
- 376. 摆动序列——【Leetcode每日刷题】
- 用R分析时间序列(time series)数据
- 【2008】 求数列最大累加和的子序列
- 机器学习-时间序列(一):日期和时间处理
- 【NLP】自然语言处理的中间序列建模
- 最长连续序列-c语言哈希表加数组界定法
- 序列相关的趣题 之二
- 时间序列挖掘-预测算法-三次指数平滑法(Holt-Winters)——三次指数平滑算法可以很好的保存时间序列数据的趋势和季节性信息
- YAML序列样式
- Python少儿编程入门篇(6)序列基础、成员和身份运算