P2290 [HNOI2004]树的计数
2024-09-05 13:53:36
P2290 [HNOI2004]树的计数
prufer序列模板题
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#define inf 2147483647
#define N 1000010
#define p(a) putchar(a)
#define For(i,a,b) for(long long i=a;i<=b;++i)
//by war
//2019.8.26
using namespace std;
long long n,sum,flag,cnt,temp,ans;
long long a[N],prime[N],tot[N];
bool vis[N];
void in(long long &x){
long long y=;char c=getchar();x=;
while(c<''||c>''){if(c=='-')y=-;c=getchar();}
while(c<=''&&c>=''){ x=(x<<)+(x<<)+c-'';c=getchar();}
x*=y;
}
void o(long long x){
if(x<){p('-');x=-x;}
if(x>)o(x/);
p(x%+'');
} void Euler(){
for(long long i=;i<=;i++){
if(!vis[i]) prime[++cnt]=i;
for(long long j=;j<=cnt&&i*prime[j]<=;j++){
vis[i*prime[j]]=;
if(i%prime[j]==)
break;
}
}
} long long ksm(long long a,long long b){
long long r=;
while(b>){
if(b&) r*=a;
a*=a;
b>>=;
}
return r;
} signed main(){
in(n);Euler();
For(i,,n){
in(a[i]),sum+=a[i]-;
if(!a[i]) flag=;
}
if(n==&&flag){
o(); return ;
}
if(sum!=n-||flag){
o(); return ;
}
For(i,,n-){
temp=i;
For(j,,cnt)
while(temp%prime[j]==){
tot[prime[j]]++;
temp/=prime[j];
}
}
For(i,,n)
For(j,,a[i]-){
temp=j;
For(k,,cnt)
while(temp%prime[k]==){
tot[prime[k]]--;
temp/=prime[k];
}
}
ans=;
For(i,,cnt)
ans*=ksm(prime[i],tot[prime[i]]);
o(ans);
return ;
}
最新文章
- 6周学习计划,攻克JavaScript难关(React/Redux/ES6 etc.)
- ORA-32004
- POJ 2674
- mybatis0204 一对多查询
- 04JS高级动态添加属性和删除属性
- 纯css3 轮播图 利用keyframes
- JQuery操作元素的属性与样式及位置 复制代码
- (转)Spring3MVC 在JSP中使用@ModelAttribute
- 解决html5中video标签无法播放mp4问题的办法
- CentOS6.5安装Maven3.2.5
- 移除元素(remove,remove_if...unique...)
- nginx安装(转发)
- Windows Server 2008 + SQL Server 2005集群
- Instantiation of bean failed; nested exception is org.springframework.beans.BeanInstantiationException: Could not instantiate bean class [com.liuyang.JDbCTemplate.PersonDao]: No default constructor fo
- postgresql-数据库网络地址存储探索
- angularjs animation
- command symbol &; mac &; emoji
- 还原JavaScript的真实历史~
- win32调试工具原理OutputDebugString以及如何获取输出信息
- FastAdmin 中使用 Oder by if 强行将某一类放到前面
热门文章
- Django rest_framework 频率控制组件
- python发送微信及企业微信消息
- day08 python文件操作
- Java中如何实现序列化,有什么意义?
- ajax json jQuery提示parsererror错误解决办法
- io.File+递归
- js过滤字符串中的html标签
- 分布式项目中增加品牌前端页面出现Uncaught Error: [$injector:modulerr] bug后的原因以及改正方式
- Frost &; Sullivan权威报告:阿里云再次领跑云WAF大中华区市场
- java-逻辑处理